在线社交网络内动态群组查询

Li WEIGANG; Edans F. O. SANDES; Jianya ZHENG; Alba C. M. A. de MELO; Lorna UDEN

doi:10.1631/jzus.C1300281

Your Location：

Home >

Browse articles >

在线社交网络内动态群组查询

计算机与自动化 | Updated：2022-05-19

- 在线社交网络内动态群组查询
- Querying dynamic communities in online social networks
- 信息与电子工程前沿（英文） 2014年15卷第2期页码：81-90
- Affiliations：
  
  1.Department of Computer Science, University of Brasilia, Brasilia 70910-900, Brazil
  2.School of Computing, Staffordshire University, Stafford ST18 0AD, UK
- Author bio：
  
  Li WEIGANG, weigang@cic.unb.br
- Funds：
  
  Project supported by the Brazilian National Council for Scientific and Technological Development (CNPq) (No. 304058/2010-6)
- DOI：10.1631/jzus.C1300281
  中图分类号： TP393.09
- 收稿：2013-10-08，
  
  修回：2014-1-15，
  
  录用：2013-12-22，
  
  纸质出版：2014-02
- Accepted：
Scan QR Code
在线社交网络内动态群组查询[J]. 信息与电子工程前沿（英文）, 2014,15(2):81-90.

Li WEIGANG, Edans F. O. SANDES, Jianya ZHENG, et al. Querying dynamic communities in online social networks[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(2): 81-90.
在线社交网络内动态群组查询[J]. 信息与电子工程前沿（英文）, 2014,15(2):81-90. DOI： 10.1631/jzus.C1300281.

Li WEIGANG, Edans F. O. SANDES, Jianya ZHENG, et al. Querying dynamic communities in online social networks[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(2): 81-90. DOI： 10.1631/jzus.C1300281.

摘要

研究目的

在线社交网络的动态群组形成具有在线即时、信息突发和传播迅速等特点，在大数据环境下及时发现有用的群组内的信息，是本专业的一项富有挑战性的工作。本文引用描述用户关系的逻辑模型(Follow Model，简称“粉丝模型”)，结合文章映射和化简(MapReduce)概念，探讨映射关注和化简粉丝(MapFollowee & ReduceFollower)机制在Hadoop系统联机实现的算法。

创新要点

在线社交网络的研究缺乏使用和方便的基础理论模型，粉丝模型(Follow Model)的建立，为研究动态群组查询和微博转发预测等提供有效的元模型。结合映射和化简(MapReduce)理念，本文算法为在线社交网络动态群组的查询，即大数据的动态查询，提供并行计算的实用性算法。

方法提亮

组成粉丝模型（Follow Model）的各类函数把微博用户关系简洁和准确地描述出来，同时具备以下三个特点：反对称与对称性、可扩展性和可组合性。这些特性的灵活应用，形成本文提出的两大类查询算法：反对称关系查询算法（reverse relation）和高阶关系查询算法（high-order relation）。

重要结论

本文研究在线社交网络，特别是Twitter和新浪微博平台的动态群组形成机理，提出描述用户间关系的逻辑模型，即粉丝模型。将此模型结合映射和化简理念，提出对这些动态群组信息查询的并行算法。特别是通过对Twitter平台内两个群组信息查询的实际检验，展示大数据环境下本文算法的有效性。

Abstract

Online social networks (OSNs) offer people the opportunity to join communities where they share a common interest or objective. This kind of community is useful for studying the human behavior

diffusion of information

and dynamics of groups. As the members of a community are always changing

an efficient solution is needed to query information in real time. This paper introduces the Follow Model to present the basic relationship between users in OSNs

and combines it with the MapReduce solution to develop new algorithms with parallel paradigms for querying. Two models for reverse relation and high-order relation of the users were implemented in the Hadoop system. Based on 75 GB message data and 26 GB relation network data from Twitter

a case study was realized using two dynamic discussion communities: #musicmonday and #beatcancer. The querying performance demonstrates that the new solution with the implementation in Hadoop significantly improves the ability to find useful information from OSNs.

关键词

Keywords

references

A. Anagnostopoulos , , , R. Kumar , , , M. Mahdian . . Influence and correlation in social networks . . Proc.14th ACM SIGKDD Int.Conf.on Knowledge Discovery and Data Mining , , 2008 . . p.7 - - 15 . . DOI: 10.1145/1401890.1401897 http://doi.org/10.1145/1401890.1401897 . .

M. Bhandarkar . . MapReduce programming with Apache Hadoop . . 24th IEEE Int.Parallel & Distributed Processing Symp. , , 2010 . . p.1 DOI: 10.1109/IPDPS.2010.5470377 http://doi.org/10.1109/IPDPS.2010.5470377 . .

A. Bialecki , , , M. Cafarella , , , D. Cutting , , , 等 . . Hadoop: a framework for running applications on large clusters built of commodity hardware . . Available from http://lucene.apache.org/hadoop , , 2005 . . .

M. Cha , , , H. Haddadi , , , F. Benevenuto , , , 等 . . Measuring user influence in Twitter: the million follower fallacy . . Proc.4th Int.AAAI Conf.on Weblogs and Social Media , , 2010 . . p.10 - - 17 . . . .

W. Chen , , , Y. Wang , , , S. Yang . . Efficient influence maximization in social networks . . Proc.15th ACM SIGKDD Int.Conf.on Knowledge Discovery and Data Mining , , 2009 . . p.199 - - 208 . . DOI: 10.1145/1557019.1557047 http://doi.org/10.1145/1557019.1557047 . .

J. Dean , , , S. Ghemawat . . MapReduce: simplified data processing on large clusters . . Commun.ACM , , 2008 . . 51 ( ( 1 ): ): 107 - - 113 . . DOI: 10.1145/1327452.1327492 http://doi.org/10.1145/1327452.1327492 . .

A. Goyal , , , F. Bonchi , , , L.V.S. Lakshmanan . . Learning influence probabilities in social networks . . Proc.3rd ACM Int.Conf.on Web Search and Data Mining , , 2010 . . p.241 - - 250 . . DOI: 10.1145/1718487.1718518 http://doi.org/10.1145/1718487.1718518 . .

G. Karypis , , , R. Aggarwal , , , V. Kumar , , , 等 . . Multilevel hypergraph partitioning: applications in VLSI domain . . IEEE Trans.VLSI , , 1999 . . 7 ( ( 1 ): ): 69 - - 79 . . DOI: 10.1109/92.748202 http://doi.org/10.1109/92.748202 . .

H. Kwak , , , C. Lee , , , H. Park , , , 等 . . What is Twitter, a social network or a news media . . Proc.19th Int.Conf.on World Wide Web , , 2010 . . p.591 - - 600 . . DOI: 10.1145/1772690.1772751 http://doi.org/10.1145/1772690.1772751 . .

D. Liben-Nowell , , , J. Kleinberg . . The link-prediction problem for social networks . . J.Amer.Soc.Inform.Sci.Technol. , , 2007 . . 58 ( ( 7 ): ): 1019 - - 1031 . . DOI: 10.1002/asi.20591 http://doi.org/10.1002/asi.20591 . .

L. Lü , , , T. Zhou . . Link prediction in complex networks: a survey . . Phys.A , , 2011 . . 390 ( ( 6 ): ): 1150 - - 1170 . . DOI: 10.1016/j.physa.2010.11.027 http://doi.org/10.1016/j.physa.2010.11.027 . .

E.F.O. Sandes , , , L. Weigang , , , A.C.M.A. de Melo . . Logical model of relationship for online social networks and performance optimization of queries . . LNCS , , 2012 . . 7651 726 - - 736 . . DOI: 10.1007/978-3-642-35063-4_59 http://doi.org/10.1007/978-3-642-35063-4_59 . .

Y. Sun , , , J. Han , , , C.C. Aggarwal , , , 等 . . When will it happen.—relationship prediction in heterogeneous information networks . . Proc.5th ACM Int.Conf.on Web Search and Data Mining , , 2012 . . p.663 - - 672 . . DOI: 10.1145/2124295.2124373 http://doi.org/10.1145/2124295.2124373 . .

J. Tang , , , J. Sun , , , C. Wang , , , 等 . . Social influence analysis in large-scale networks . . Proc.15th ACM SIGKDD Int.Conf.on Knowledge Discovery and Data Mining , , 2009 . . p.807 - - 816 . . DOI: 10.1145/1557019.1557108 http://doi.org/10.1145/1557019.1557108 . .

Z. Tang , , , H. Lin , , , K. Li , , , 等 . . Acolyte: an in-memory social network query system . . Proc.13th Int.Conf.on Web Information Systems Engineering , , 2012 . . p.755 - - 763 . . DOI: 10.1007/978-3-642-35063-4_62 http://doi.org/10.1007/978-3-642-35063-4_62 . .

M. Theobald , , , H. Bast , , , D. Majumdar , , , 等 . . TopX: efficient and versatile top- k query processing for semi-structured data . . VLDB J. , , 2008 . . 17 ( ( 1 ): ): 81 - - 115 . . DOI: 10.1007/s00778-007-0072-z http://doi.org/10.1007/s00778-007-0072-z . .

L. Weigang , , , J. Zheng , , , G. Liu . . W-entropy method to measure the influence of the members from social networks . . Int.J.Web Eng.Technol., in press , , 2013 . . .

J. Yang , , , J. Leskovec . . Patterns of temporal variation in online media . . Proc.4th ACM Int.Conf.on Web Search and Data Mining , , 2011 . . p.177 - - 186 . . DOI: 10.1145/1935826.1935863 http://doi.org/10.1145/1935826.1935863 . .

Z.K. Zhang , , , C. Liu . . A hypergraph model of social tagging networks . . J.Stat.Mech. , , 2010 . . 2010 ( ( 10 ): ): P10005 DOI: 10.1088/1742-5468/2010/10/P10005 http://doi.org/10.1088/1742-5468/2010/10/P10005 . .

J. Zheng , , , L. Weigang , , , L. Uden . . Top-X querying in online social networks with MapReduce solution . . Proc.8th Int.Conf.on Knowledge Management in Organizations , , 2014 . . p.397 - - 410 . . DOI: 10.1007/978-94-007-7287-8_32 http://doi.org/10.1007/978-94-007-7287-8_32 . .

L. Zheng , , , X. Zhou , , , Z. Lin , , , 等 . . Accelerating queries over microblog dataset via grouping and indexing techniques . . Proc.13th Int.Conf.on Web Information Systems Engineering , , 2012 . . p.764 - - 770 . . DOI: 10.1007/978-3-642-35063-4_63 http://doi.org/10.1007/978-3-642-35063-4_63 . .

F. Zhu , , , J. Liu , , , L. Xu . . A fast and high throughput SQL query system for big data . . Proc.13th Int.Conf.on Web Information Systems Engineering , , 2012 . . p.783 - - 788 . . DOI: 10.1007/978-3-642-35063-4_66 http://doi.org/10.1007/978-3-642-35063-4_66 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Dr. Hadoop: an infinite scalable metadata management for Hadoop—How the baby elephant becomes immortal