大尺度在线社会网络结构研究
|
摘要
在线社会网络（OSN：Online Social Network）是由大规模（千万级以上）互联网用户及其相对稳定的联接关系构成的集合，目前已经成为人们日常交流的重要方式。此类网络在一定程度上，可以看作是现实社会关系（如共同兴趣者、家人及朋友等）在网络空间的一种映射，是物理世界在网络空间的重现。在线社会网络由早期的Email网络发展到现在，规模越来越庞大。在可预见的未来，在线社会网络会越来越多地影响人类的生活，改变物理世界中人类社会的组织结构，影响人类社会的发展进程。目前，在线社会网络已成为业界和学术界关注的热点。
在在线社会网络的研究中，主要分为三部分研究内容：（1）网络节点如何相互链接而构成在线社会网络的拓扑结构；（2）网络用户在这样的网络中发布消息的类型；（3）消息是如何在网络拓扑之上传播的。由于在线社会网络发展迅猛，用户规模庞大，因此，认识在线社会网络的结构，实时发现用户发布的消息类型，以及预测消息如何在网络拓扑上传播都成为计算机研究领域的挑战。然而，发现用户是如何链接而构成在线社会网络的拓扑机构成为认识在线社会网络，并进行其他研究的基础。
以MySql和Hadoop为基础建立一个海量数据爬取和存储系统，在大约3,000万用户数据的基础之上，通过数据分析和挖掘，从用户特征和网络拓扑特征入手，分析了新浪微博的系统特征，指出新浪微博是一个大尺度，自组织，小世界，不均衡，高动态的网络。新浪微博拥有超过3.5亿的用户，并且用户是通过自组织的方法来构建网络拓扑，因此新浪微博是一个大尺度自组织的网络。同时，测量结果显示用户之间的平均距离在6步左右，显示新浪微博是一个小世界网络。微博用户之间的关注关系变动频繁，用户每天改变2个左右的关注用户，而有些用户的粉丝数目每天变化在3,000左右，显示新浪微博是一个高动态的网络。新浪微博用户在地域/性别分布，粉丝/关注数目分布，相互关注率方面又显示出明显的不均衡特征。依据这些特征，提出把在线社会网络分为两种基本类型：信息驱动型在线社会网络和关系驱动型在线社会网络。结果明确显示新浪微博与Facebook等关系驱动型社会网络不同，同时，在互相关注率等特征方面，新浪微博和Twitter也有较大区别。
为了更深刻的理解新浪微博的拓扑结构，识别拓扑结构内部的社区，提出FriendFinder算法。该算法以社会网络中存在的三元闭包理论为基础，使用局部搜索和启发式算法，来识别网络中含有的社区结构。该算法首先利用最大度来寻找两个节点作为初始社区，分析社区的邻居节点集合，把合适的社区邻居节点加入已经存在的社区中，对于新形成的社区，迭代以上规则，直至社区不能再扩大为止，一个社区便形成了。和经典的社区划分算法相比，FriendFinder具有较好的时间复杂度，同时社区识别的准确度较高，并且该算法具有一定的可并行性，能够处理有向和无向网络，同时可以实现快速对网络拓扑结构的划分。在测试中，发现了新浪微博中存在的7个规模较大的社区，包含31,152用户。
在新浪微博的网络特征以及社区特征的基础之上，拟合新浪微博网络中用户的关注数目曲线，建立用户关注数目函数。根据新浪微博的特征，使用用户粉丝数目作为标准，把新浪微博网络分为核心网络和外围网络。在核心网络中，128.5万的用户吸引了全网36.71%的关注链接，同时核心用户的关注中57.68%指向核心网络内部。通过分析新浪微博的自组织规则，发现了新浪微博用户的链接机制，提出LinkProbability算法来计算用户的被选择概率，利用真实的新浪微博拓扑特征的参数和新浪微博中关注关系形成的机制，Group-Based演化模型可以用来描述新浪微博的拓扑结构以及演化特征。Group-Based演化模型借鉴经典的演化模型框架，在候选节点集合选择以及候选节点被选择的概率方面使用新浪微博中的用户链接机制，因此能更好的反映新浪微博的拓扑结构。
在全面理解和认识新浪微博的拓扑结构和其形成机制的基础之上，不考虑主观因素，仅以新浪微博的拓扑特征为基础，设计WeiRank算法用以量化新浪微博中用户的重要性。WeiRank算法模拟人类社会中存在的投票方法，使用迭代的方法来为每个节点的投票赋予不同的权重，计算每个用户被投票的次数和每次投票的权重来量化不同用户所具有的不同的网络影响力。和HITS以及PageRank等经典排序算法相比，WeiRank算法能更好的对社会网络中的用户进行影响力排序，并完成对新浪微博中粉丝数最多的前150万人进行排序。
It's long been said that the revolutions in communications and information technologyhad given birth to a virtual world. Now it comes true, and our software, computers and cellphones have become woven into every aspect of our lives. OSNs make the cyberspace realand uses depend on it every single day. Most web sites put Facebook and twitter icons ontheir home pages, which makes the World Wide Web more social and more real-time.OSN becomes an important part of our lives, which attract many users and build a virtualworld, which is a map of the real world. Users of such systems will continue grow, andthese systems will change the real world, for they are good communication applicationsafter Email and Instant Messenger(IM), which have made us more interconnected than atany time in human history. Thus, OSN have received significant attention from bothindustry and academia. More and more researchers pay attention to OSN, and manypapers have been published up to now.
In microblog system, users connect with each other and form the overlay of the system;users generate tweets and share them with their followers; then, the tweets are spread overthe overlay. Hence, there are three basic questions in microblog system:(i) How do usersconnect with each other and form the network;(ii) what do users talk about in microblog;and (iii) how do the tweets transmit through the network. The goal of this paper is only tostudy how do users connect with each other and form the network using standard complexnetwork techniques. Topic detection and hot topic prediction are very important researchcontent in online social network. However, they are beyond the scope of this paper.
This paper spends about two years to observe the overlay of Weibo persistently whichis less studied before, and to make the characteristics of Weibo s network clear, which isthe basic research before researchers could talk about the tweets diffusion and hot topicdetection. All users in Weibo are Chinese and they enjoy a different culture. Meanwhile, itis a map of the real social of China, and understanding its overlay characteristics couldmake us infer the real structure of Chinese society and estimate the influence to the realworld.
Our data shows that Weibo has a core/periphery structure, which makes it a goodsystem for information sharing. Then we give one general model and one detail model todescribe Weibo s structure. For the imbalanced development of economy of China, mostusers in Weibo live in the developed cities of the developed provinces, and their activetime is from6AM to24PM. Less than0.03%users draw about30%following links inWeibo, which is not analyzed quantitatively in Twitter, and this is a novel feather ofWeibo. Compared with Twitter, the reciprocal rates of users in Weibo are lower. Thispaper also first finds users with more followers and their followings often follow eachother, meanwhile, they like to post more tweets. The distribution of users followingsand followers partly fits to the power-law distribution. The overlay of Weibo is dynamicalbecause of new users join and existing users change. The reciprocal rate of users islower than Twitter s. This paper proves the CPL is very short and this theory could bewidely used in OSN. We also show the characteristics of sub-groups in Weibo and presenta method to rank the importance of users in Weibo. In addition, we present a methodnamed Friendfinder to detect communities in Weibo, and present a technique namedWeiRank to rank users in Weibo.
In conclusion, this paper makes insight into Weibo, and show the characteristics ofWeibo s overlay systematically and comprehensively. As far as we know, this is the firstquantitative study on Weibo s overlay particularly. Understanding the characteristics ofWeibo s overlay is the basic research before other researchers talk about the diffusion oftweets, hot topic prediction and so on, and it also uncovers the characteristics of the realChinese society. Our results are helpful for OSN operators and other researchers on OSNs.Finally, hot topic detection and diffusion of tweets are the two areas for our future workwhich are based on the structure of Weibo, and such researches could make all thecharacteristics of Weibo come to light drastically.
在在线社会网络的研究中，主要分为三部分研究内容：（1）网络节点如何相互链接而构成在线社会网络的拓扑结构；（2）网络用户在这样的网络中发布消息的类型；（3）消息是如何在网络拓扑之上传播的。由于在线社会网络发展迅猛，用户规模庞大，因此，认识在线社会网络的结构，实时发现用户发布的消息类型，以及预测消息如何在网络拓扑上传播都成为计算机研究领域的挑战。然而，发现用户是如何链接而构成在线社会网络的拓扑机构成为认识在线社会网络，并进行其他研究的基础。
以MySql和Hadoop为基础建立一个海量数据爬取和存储系统，在大约3,000万用户数据的基础之上，通过数据分析和挖掘，从用户特征和网络拓扑特征入手，分析了新浪微博的系统特征，指出新浪微博是一个大尺度，自组织，小世界，不均衡，高动态的网络。新浪微博拥有超过3.5亿的用户，并且用户是通过自组织的方法来构建网络拓扑，因此新浪微博是一个大尺度自组织的网络。同时，测量结果显示用户之间的平均距离在6步左右，显示新浪微博是一个小世界网络。微博用户之间的关注关系变动频繁，用户每天改变2个左右的关注用户，而有些用户的粉丝数目每天变化在3,000左右，显示新浪微博是一个高动态的网络。新浪微博用户在地域/性别分布，粉丝/关注数目分布，相互关注率方面又显示出明显的不均衡特征。依据这些特征，提出把在线社会网络分为两种基本类型：信息驱动型在线社会网络和关系驱动型在线社会网络。结果明确显示新浪微博与Facebook等关系驱动型社会网络不同，同时，在互相关注率等特征方面，新浪微博和Twitter也有较大区别。
为了更深刻的理解新浪微博的拓扑结构，识别拓扑结构内部的社区，提出FriendFinder算法。该算法以社会网络中存在的三元闭包理论为基础，使用局部搜索和启发式算法，来识别网络中含有的社区结构。该算法首先利用最大度来寻找两个节点作为初始社区，分析社区的邻居节点集合，把合适的社区邻居节点加入已经存在的社区中，对于新形成的社区，迭代以上规则，直至社区不能再扩大为止，一个社区便形成了。和经典的社区划分算法相比，FriendFinder具有较好的时间复杂度，同时社区识别的准确度较高，并且该算法具有一定的可并行性，能够处理有向和无向网络，同时可以实现快速对网络拓扑结构的划分。在测试中，发现了新浪微博中存在的7个规模较大的社区，包含31,152用户。
在新浪微博的网络特征以及社区特征的基础之上，拟合新浪微博网络中用户的关注数目曲线，建立用户关注数目函数。根据新浪微博的特征，使用用户粉丝数目作为标准，把新浪微博网络分为核心网络和外围网络。在核心网络中，128.5万的用户吸引了全网36.71%的关注链接，同时核心用户的关注中57.68%指向核心网络内部。通过分析新浪微博的自组织规则，发现了新浪微博用户的链接机制，提出LinkProbability算法来计算用户的被选择概率，利用真实的新浪微博拓扑特征的参数和新浪微博中关注关系形成的机制，Group-Based演化模型可以用来描述新浪微博的拓扑结构以及演化特征。Group-Based演化模型借鉴经典的演化模型框架，在候选节点集合选择以及候选节点被选择的概率方面使用新浪微博中的用户链接机制，因此能更好的反映新浪微博的拓扑结构。
在全面理解和认识新浪微博的拓扑结构和其形成机制的基础之上，不考虑主观因素，仅以新浪微博的拓扑特征为基础，设计WeiRank算法用以量化新浪微博中用户的重要性。WeiRank算法模拟人类社会中存在的投票方法，使用迭代的方法来为每个节点的投票赋予不同的权重，计算每个用户被投票的次数和每次投票的权重来量化不同用户所具有的不同的网络影响力。和HITS以及PageRank等经典排序算法相比，WeiRank算法能更好的对社会网络中的用户进行影响力排序，并完成对新浪微博中粉丝数最多的前150万人进行排序。
It's long been said that the revolutions in communications and information technologyhad given birth to a virtual world. Now it comes true, and our software, computers and cellphones have become woven into every aspect of our lives. OSNs make the cyberspace realand uses depend on it every single day. Most web sites put Facebook and twitter icons ontheir home pages, which makes the World Wide Web more social and more real-time.OSN becomes an important part of our lives, which attract many users and build a virtualworld, which is a map of the real world. Users of such systems will continue grow, andthese systems will change the real world, for they are good communication applicationsafter Email and Instant Messenger(IM), which have made us more interconnected than atany time in human history. Thus, OSN have received significant attention from bothindustry and academia. More and more researchers pay attention to OSN, and manypapers have been published up to now.
In microblog system, users connect with each other and form the overlay of the system;users generate tweets and share them with their followers; then, the tweets are spread overthe overlay. Hence, there are three basic questions in microblog system:(i) How do usersconnect with each other and form the network;(ii) what do users talk about in microblog;and (iii) how do the tweets transmit through the network. The goal of this paper is only tostudy how do users connect with each other and form the network using standard complexnetwork techniques. Topic detection and hot topic prediction are very important researchcontent in online social network. However, they are beyond the scope of this paper.
This paper spends about two years to observe the overlay of Weibo persistently whichis less studied before, and to make the characteristics of Weibo s network clear, which isthe basic research before researchers could talk about the tweets diffusion and hot topicdetection. All users in Weibo are Chinese and they enjoy a different culture. Meanwhile, itis a map of the real social of China, and understanding its overlay characteristics couldmake us infer the real structure of Chinese society and estimate the influence to the realworld.
Our data shows that Weibo has a core/periphery structure, which makes it a goodsystem for information sharing. Then we give one general model and one detail model todescribe Weibo s structure. For the imbalanced development of economy of China, mostusers in Weibo live in the developed cities of the developed provinces, and their activetime is from6AM to24PM. Less than0.03%users draw about30%following links inWeibo, which is not analyzed quantitatively in Twitter, and this is a novel feather ofWeibo. Compared with Twitter, the reciprocal rates of users in Weibo are lower. Thispaper also first finds users with more followers and their followings often follow eachother, meanwhile, they like to post more tweets. The distribution of users followingsand followers partly fits to the power-law distribution. The overlay of Weibo is dynamicalbecause of new users join and existing users change. The reciprocal rate of users islower than Twitter s. This paper proves the CPL is very short and this theory could bewidely used in OSN. We also show the characteristics of sub-groups in Weibo and presenta method to rank the importance of users in Weibo. In addition, we present a methodnamed Friendfinder to detect communities in Weibo, and present a technique namedWeiRank to rank users in Weibo.
In conclusion, this paper makes insight into Weibo, and show the characteristics ofWeibo s overlay systematically and comprehensively. As far as we know, this is the firstquantitative study on Weibo s overlay particularly. Understanding the characteristics ofWeibo s overlay is the basic research before other researchers talk about the diffusion oftweets, hot topic prediction and so on, and it also uncovers the characteristics of the realChinese society. Our results are helpful for OSN operators and other researchers on OSNs.Finally, hot topic detection and diffusion of tweets are the two areas for our future workwhich are based on the structure of Weibo, and such researches could make all thecharacteristics of Weibo come to light drastically.
引文
[1] S. Milgram.The small world problem.Psychology today,1967,2(1):60-67
[2] P.S. Dodds, R. Muhamad, D.J. Watts.An experimental study of search in global social networks. science,2003,301(5634):827-829
[3] M.S. Granovetter.The strength of weak ties.American Journal of Sociology,1973,1360-1380
[4]D.J. Watts, S.H. Strogatz.Collective dynamics of ‘small-world’networks.Nature,1998,393(6684):440-442
[5] A.L. Barabási, R. Albert.Emergence of scaling in random networks.science,1999,286(5439):509
[6] John Markoff. An Internet Pioneer Ponders the Next Revolution. The New York.1999Times. Archived from the original on22September2008. Retrieved20September2008.
[7] C. Partridge.The technical development of internet email. Annals of the History of Computing, IEEE,2008,30(2):3-29
[8] Crosby, Kip. CONVIVIAL CYBERNETIC DEVICES. The ANALYTICAL ENGINE (Computer HistoryAssociation of California)3(1).1995. ISSN1071-6351
[9] T.V. Vleck.Electronic Mail and Text Messaging in CTSS,1965–1973. IEEE Annals of the History ofComputing,2012,34(1):4-6
[10] R. Blood.Weblogs: a history and perspective.Rebecca's Pocket,2000,7(9):2000
[11] K. Beuerlein.sixdegrees. com Where networking is everything.LINK UP-MINNEAPOLIS THENMEDFORD,2000,17(5):23-23
[12] D.M. Boyd.Friendster and publicly articulated social networking.in:ACM Press,2004.
[13] J. Snyder, D. Carpenter, G.J. Slauson.MySpace. com–A social networking site and social contracttheory.Director,2006,07
[14] K. Lewis,J. Kaufman,M. Gonzalez et al.Tastes, ties, and time: A new social network dataset usingFacebook. com.Social networks,2008,30(4):330-342
[15] A. Java,X. Song,T. Finin et al.Why we twitter: understanding microblogging usage andcommunities.in:ACM,2007.56-65
[16] S. Ovadia.An Early Introduction to the Google+Social Networking Project.Behavioral&SocialSciences Librarian,2011,30(4):259-263
[17] C. Baldwin, J. Saba.Renren's big day, a prelude to Facebook IPO.Reuters, May,2011,4
[18] X. Li.Syracuse Science&Technology Law Reporter.Syracuse Science and Technology Law Reporter,2011,1
[19] T. Wasserman.Google+Hits25Million Visitors, Gets More Sticky [Study]. Mashable Social Media,2011,2
[20]高弋坤.新浪微博用户数再创新高.通信世界,2012,46:11-11
[21]易观国际.2011年第2季度中国微博市场季度监测. Oct,2011
[22] CNNIC.第29次中国互联网络发展状况调查统计报告,2012,
[23]娄成武,刘力锐.论网络政治动员:一种非对称态势.政治学研究,2010,2(75)
[24]美国国土安全部.隐私法执行评估. Nov,2011
[25] N. Shachtman.Exclusive: US spies buy stake in firm that monitors blogs, tweets.Danger Room, Wired.com,2009,
[26] M E J Newman.The structure and function of networks. Computer Physics Communications,2002,147(1):40-45
[27]Rim Dunbar.How many friends does one person need.Royal Society for the Encouragement of the Arts,Manufactures and Commerce, London,2010
[28]K. Kaneko. Theory and applications of coupled map lattices: John Wiley&Sons,1993
[29]P. Erd s,A. Rényi. On the evolution of random graphs:Akad. Kiadó,1960
[30]Z. Burda, J. Jurkiewicz, A. Krzywicki.Statistical mechanics of random graphs.Physica A: StatisticalMechanics and its Applications,2004,344(1):56-61
[31]B. Bollobás.Random graphs.1985.Academic, London,2001,
[32]D.B. West.Introduction to Graph Theory.1996.Prentiss Hall, Upper Saddle River, NJ,1996,
[33]A. Barrat, M. Weigt.On the properties of small-world network models.The European Physical JournalB-Condensed Matter and Complex Systems,2000,13(3):547-560
[34]M.E.J. Newman, Dj Watts.Renormalization group analysis of the small-world network model.PhysicsLetters A,1999,263(4-6):341-346
[35]R. Monasson.Diffusion, localization and dispersion relations on “small-world” lattices.The EuropeanPhysical Journal B-Condensed Matter and Complex Systems,1999,12(4):555-567
[36]W. Aiello, F. Chung, L. Lu.A random graph model for massive graphs.in:Acm,2000.171-180
[37]G. Bianconi, A.L. Barabási.Competition and multiscaling in evolving networks.EPL (EurophysicsLetters),2001,54(436)
[38]R Kumar, J Novak, A Tomkins.Structure and evolution of online social networks.Link Mining: Models,Algorithms, and Applications,2010,337-357
[39]A Mislove,M Marcon,Kp Gummadi et al.Measurement and analysis of online social networks.in:ACM,2007.29-42
[40]A. Mislove,H.S. Koppula,K.P. Gummadi et al.Growth of the flickr social network.in:ACM,2008.25-30
[41]M. Gjoka,M. Kurant,C.T. Butts et al.Practical Recommendations on Crawling Online Social Networks.Selected Areas in Communications, IEEE Journal on,2011,29(9):1872-1892
[42]B. Viswanath,A. Mislove,M. Cha et al.On the evolution of user interaction in facebook.in:ACM,2009.37-42
[43]J.M. Kleinberg.Challenges in mining social network data: processes, privacy, and paradoxes.in:ACM,2007.4-5
[44]M. Fiedler.Algebraic Connectivity of Graphs.Czechoslovak Math. J,1973,23(298-305
[45]A. Pothen, H.D. Simon, K.P. Liou.Partitioning sparse matrices with eigenvectors of graphs.SIAM J.MATRIX ANAL. APPLIC.,1990,11(3):430-452
[46]B.W. Kernighan, S. Lin.An efficient heuristic procedure for partitioning graphs.Bell System TechnicalJournal,1970,49(2):291-307
[47]M. Girvan, M.E.J. Newman.Community structure in social and biological networks.Proceedings of theNational Academy of Sciences,2002,99(12):7821
[48]J.R. Tyler, D.M. Wilkinson, B.A. Huberman.E-mail as spectroscopy: Automated discovery ofcommunity structure within organizations.The Information Society,2005,21(2):143-153
[49]F. Radicchi,C. Castellano,F. Cecconi et al.Defining and identifying communities in networks.Proceedings of the National Academy of Sciences of the United States of America,2004,101(9):2658
[50]H. Tsuchiura,M. Ogata,Y. Tanaka et al.Electronic states around a vortex core in high-T_{c}superconductors based on the tJ model.Physical Review B,2003,68(1):012509
[51]S. Fortunato, V. Latora, M. Marchiori.Method to find community structures based on informationcentrality.Physical review E,2004,70(5):056104
[52]J. Duch, A. Arenas.Community detection in complex networks using extremal optimization.Physicalreview E,2005,72(2):027104
[53]F. Wu, B.A. Huberman.Finding communities in linear time: a physics approach.The European PhysicalJournal B-Condensed Matter and Complex Systems,2004,38(2):331-338
[54]M. Rosvall, C.T. Bergstrom.Maps of random walks on complex networks reveal community structure.Proceedings of the National Academy of Sciences,2008,105(4):1118
[55]L. Donetti, M.A. Munoz.Detecting network communities: a new systematic and efficientalgorithm.Journal of Statistical Mechanics: Theory and Experiment,2004,2004(P10012)
[56]M.E.J. Newman.Fast algorithm for detecting community structure in networks.Physical reviewE,2004,69(6):066133
[57]A. Clauset, M.E.J. Newman, C. Moore.Finding community structure in very large networks.Physicalreview E,2004,70(6):066111
[58]U.N. Raghavan, R. Albert, S. Kumara.Near linear time algorithm to detect community structures inlarge-scale networks.Physical review E,2007,76(3):036106
[59]V.D. Blondel,J.L. Guillaume,R. Lambiotte et al.Fast unfolding of communities in large networks.Journalof Statistical Mechanics: Theory and Experiment,2008,2008(P10008
[60]G. Palla,I. Derényi,I. Farkas et al.Uncovering the overlapping community structure of complex networksin nature and society.Nature,2005,435(7043):814-818
[61]E. Garfield.The history and meaning of the journal impact factor.JAMA: the journal of the AmericanMedical Association,2006,295(1):90
[62]G. Pinski, F. Narin.Citation influence for journal aggregates of scientific publications: Theory, withapplication to the literature of physics.Information Processing&Management,1976,12(5):297-312
[63]J.M. Kleinberg.Authoritative sources in a hyperlinked environment.Journal of the ACM(JACM),1999,46(5):604-632
[64]L. Page,S. Brin,R. Motwani et al.The PageRank citation ranking: Bringing order to the web,1999,
[65]R. Soricut, A. Echihabi.Trustrank: Inducing trust in automatic translations via ranking.in:Associationfor Computational Linguistics,2010.612-621
[66]K. Bharat, G.A. Mihaila.When experts agree: Using non-affiliated experts to rank populartopics.in:ACM,2001.597-602
[67]J. Kincaid.EdgeRank: The secret sauce that makes Facebook’s news feed tick.TechCrunch,2010.
[68]Hamed Haddadi Meeyoung Cha, Fabr′cio Benevenuto,Krishna P. Gummadi.Measuring User Influencein Twitter: The Million Follower Fallacy.International Conference on Weblogs and Social Media,2010,
[69]Ee-Peng Lim Jianshu Weng, Jing Jiang Qi He.TwitterRank Finding Topic-sensitive InfluentialTwitterers.Web Search and Data Mining,2010,
[70]H Kwak,C Lee,H Park et al.What is Twitter, a social network or a news media?in:ACM,2010.591-600
[71]S. Ye, S. Wu.Measuring message propagation and social influence on Twitter. com.SocialInformatics,2010,216-231
[72]A. Goyal, F. Bonchi, L.V.S. Lakshmanan.Learning influence probabilities in social networks.in:ACM,2010.241-250
[73]E. Bakshy,J.M. Hofman,W.A. Mason et al.Everyone's an influencer: quantifying influence ontwitter.in:ACM,2011.65-74
[74]Mit Technology Review.New Algorithm for Measuring the Human Power level,2011,
[75] L. Euler.Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarumPetropolitanae,1741,8(128-140)
[76]C. Bird,A. Gourley,P. Devanbu et al.Mining email social networks.in:ACM,2006.137-143
[77]P.A. Wagstrom, J.D. Herbsleb, K. Carley.A social network approach to free/open source softwaresimulation.in:2005.16-23
[78]K. Crowston, J. Howison.The social structure of free and open source software development.FirstMonday,2005,10(2-7):
[79]L. Zhou,J. Ding,Y. Wang et al.The Social Network Mining of BBS.Journal of networks,2009,4(4):298-305
[80] S.P. Borgatti, M.G. Everett, L.C. Freeman.Ucinet for Windows: Software for social network analysis.Harvard Analytic Technologies,2002,2006
[81]K.I. Goh,Y.H. Eom,H. Jeong et al.Structure and evolution of online social relationships: Heterogeneityin unrestricted discussions.Physical review E,2006,73(6):066123
[82]M.C. Green,J. Hilken,H. Friedman et al.Communication Via Instant Messenger: Short‐and Long‐Term Effects.Journal of Applied Social Psychology,2005,35(3):445-462
[83]A. Miura, K. Yamashita.Psychological and social influences on blog writing: An online survey of blogauthors in Japan.Journal of Computer‐Mediated Communication,2007,12(4):1452-1471
[84]A. Chin, M. Chignell.A social hypertext model for finding community in blogs.in:ACM,2006.11-22
[85]S. Wu,J.M. Hofman,W.A. Mason et al.Who says what to whom on twitter.in:ACM,2011.705-714
[86]B Krishnamurthy, P Gill, M Arlitt.A few chirps about twitter.in:ACM,2008.19-24
[87]L. Backstrom,P. Boldi,M. Rosa et al.Four Degrees of Separation.Arxiv preprint arXiv:1111.4570,2011,
[88]B. Fields,K. Jacobson,C. Rhodes et al.Analysis and Exploitation of Musician Social Networks forRecommendation and Discovery.Ieee Transactions on Multimedia,2011,13(4):674-686
[89]微博API. http://open.weibo.com/
[90] Z. Guo, Z. Li, H. Tu, and D. Xie. Detecting and Modeling the Structure of a Large-Scale Microblog.Springer Lecture Notes in Electrical Engineering (LNEE)-Proceedings of2012International Conference onFuture Information Technology. Vancouver, Canada.
[91]用户统计.http://it.sohu.com/20111109/n325056186.shtml
[92]中华人民共和国国家统计局.2010年第六次全国人口普查主要数据公报.2011.
[93]赵嘉怡.女性撑起社交网站半边天?互联网周刊,2012,7:38-39
[94] Z.Guo, Z.Li, H.Tu and L.Li. Characterizing user behavior in Weibo. The3rd International Conferenceon Mobile, Ubiquitous, and Intelligent Computing.2012,Vancouver, Canada.
[95]孟波.新浪微博:一场正在发生的信息传播变革.南方传媒研究第21辑,南方日报出版社,2009
[96] QQ在线人数.http://im.qq.com/online.shtml#qq
[97]X. Hei,C. Liang,J. Liang et al.A measurement study of a large-scale P2P IPTV system.Multimedia, IEEETransactions on,2007,9(8):1672-1687
[98]10Fascinating Facebook Facts.http://mashable.com/2010/07/22/facebook-facts/
[99]Ba Huberman, Dm Romero, F Wu.Social networks that matter: Twitter under the microscope.FirstMonday,2009,14(1):8
[100] P. Van Mieghem, Performance Analysis of Communications Networks and Systems.Cambridge, U.K.: Cambridge Univ. Press,2006.
[101] R.K. Merton.The Matthew effect in science.science,1968,159(3810):56-63
[102]V. Batagelj, A. Mrvar.Pajek—analysis and visualization of large networks.Graph drawing software,2004,77-103
[103]A. Rapoport.Spread of information through a population with socio-structural bias: I. Assumption oftransitivity.Bulletin of Mathematical Biology,1953,15(4):523-533
[104]R. Guimera, L.A.N. Amaral.Functional cartography of complex metabolic networks.Nature,2005,433(7028):895-900
[105]Y.Y. Ahn, J.P. Bagrow, S. Lehmann.Link communities reveal multiscale complexity in networks.Nature,2010,466(7307):761-764
[106]S. Fortunato, M. Barthelemy.Resolution limit in community detection.Proceedings of the NationalAcademy of Sciences,2007,104(1):36
[107]Lynn Smith-Lovin Miller Mcpherson, And, James M Cook.Birds of a feather Homophily in socialnetworks,2001,
[108] J. Paul.(1901),étude comparative de la distribution florale dans une portion des Alpes et des Jura,Bulletin de la SociétéVaudoise des Sciences Naturelles37:547–579.
[109]M. E. J. Newman, M. Girvan.Finding and evaluating community structure in networks.Physicalreview E,2004,69(2):
[110]W.W. Zachary.An information flow model for conflict and fission in small groups.Journal ofanthropological research,1977,452-473
[111]D. Lusseau, M.E.J. Newman.Identifying the role that animals play in their social networks.Proceedingsof the Royal Society of London. Series B: Biological Sciences,2004,271(Suppl6):S477-S481
[112]A. Lancichinetti, S. Fortunato, F. Radicchi.Benchmark graphs for testing community detectionalgorithms.Physical review E,2008,78(4):046110
[113]L. Danon,A. Díaz-Guilera,J. Duch et al.Comparing community structure identification.Journal ofStatistical Mechanics: Theory and Experiment,2005,2005(P09008)
[114]Z. Guo, Z. Li, H. Tu.Sina Microblog: An Information-Driven Online Social Network. in:IEEE,2011.160-167
[115]A.N. Langville, C.D. Meyer, P. Fern ndez.Google’s pagerank and beyond: The science of searchengine rankings.The Mathematical Intelligencer,2008,30(1):68-69
[116]X. Li, G. Chen.A local-world evolving network model.Physica A: Statistical Mechanics and itsApplications,2003,328(1):274-286
[117]P. Chen,H. Xie,S. Maslovet al.Finding scientific gems with Google’s PageRank algorithm.Journal ofInformetrics,2007,1(1):8-15
[2] P.S. Dodds, R. Muhamad, D.J. Watts.An experimental study of search in global social networks. science,2003,301(5634):827-829
[3] M.S. Granovetter.The strength of weak ties.American Journal of Sociology,1973,1360-1380
[4]D.J. Watts, S.H. Strogatz.Collective dynamics of ‘small-world’networks.Nature,1998,393(6684):440-442
[5] A.L. Barabási, R. Albert.Emergence of scaling in random networks.science,1999,286(5439):509
[6] John Markoff. An Internet Pioneer Ponders the Next Revolution. The New York.1999Times. Archived from the original on22September2008. Retrieved20September2008.
[7] C. Partridge.The technical development of internet email. Annals of the History of Computing, IEEE,2008,30(2):3-29
[8] Crosby, Kip. CONVIVIAL CYBERNETIC DEVICES. The ANALYTICAL ENGINE (Computer HistoryAssociation of California)3(1).1995. ISSN1071-6351
[9] T.V. Vleck.Electronic Mail and Text Messaging in CTSS,1965–1973. IEEE Annals of the History ofComputing,2012,34(1):4-6
[10] R. Blood.Weblogs: a history and perspective.Rebecca's Pocket,2000,7(9):2000
[11] K. Beuerlein.sixdegrees. com Where networking is everything.LINK UP-MINNEAPOLIS THENMEDFORD,2000,17(5):23-23
[12] D.M. Boyd.Friendster and publicly articulated social networking.in:ACM Press,2004.
[13] J. Snyder, D. Carpenter, G.J. Slauson.MySpace. com–A social networking site and social contracttheory.Director,2006,07
[14] K. Lewis,J. Kaufman,M. Gonzalez et al.Tastes, ties, and time: A new social network dataset usingFacebook. com.Social networks,2008,30(4):330-342
[15] A. Java,X. Song,T. Finin et al.Why we twitter: understanding microblogging usage andcommunities.in:ACM,2007.56-65
[16] S. Ovadia.An Early Introduction to the Google+Social Networking Project.Behavioral&SocialSciences Librarian,2011,30(4):259-263
[17] C. Baldwin, J. Saba.Renren's big day, a prelude to Facebook IPO.Reuters, May,2011,4
[18] X. Li.Syracuse Science&Technology Law Reporter.Syracuse Science and Technology Law Reporter,2011,1
[19] T. Wasserman.Google+Hits25Million Visitors, Gets More Sticky [Study]. Mashable Social Media,2011,2
[20]高弋坤.新浪微博用户数再创新高.通信世界,2012,46:11-11
[21]易观国际.2011年第2季度中国微博市场季度监测. Oct,2011
[22] CNNIC.第29次中国互联网络发展状况调查统计报告,2012,
[23]娄成武,刘力锐.论网络政治动员:一种非对称态势.政治学研究,2010,2(75)
[24]美国国土安全部.隐私法执行评估. Nov,2011
[25] N. Shachtman.Exclusive: US spies buy stake in firm that monitors blogs, tweets.Danger Room, Wired.com,2009,
[26] M E J Newman.The structure and function of networks. Computer Physics Communications,2002,147(1):40-45
[27]Rim Dunbar.How many friends does one person need.Royal Society for the Encouragement of the Arts,Manufactures and Commerce, London,2010
[28]K. Kaneko. Theory and applications of coupled map lattices: John Wiley&Sons,1993
[29]P. Erd s,A. Rényi. On the evolution of random graphs:Akad. Kiadó,1960
[30]Z. Burda, J. Jurkiewicz, A. Krzywicki.Statistical mechanics of random graphs.Physica A: StatisticalMechanics and its Applications,2004,344(1):56-61
[31]B. Bollobás.Random graphs.1985.Academic, London,2001,
[32]D.B. West.Introduction to Graph Theory.1996.Prentiss Hall, Upper Saddle River, NJ,1996,
[33]A. Barrat, M. Weigt.On the properties of small-world network models.The European Physical JournalB-Condensed Matter and Complex Systems,2000,13(3):547-560
[34]M.E.J. Newman, Dj Watts.Renormalization group analysis of the small-world network model.PhysicsLetters A,1999,263(4-6):341-346
[35]R. Monasson.Diffusion, localization and dispersion relations on “small-world” lattices.The EuropeanPhysical Journal B-Condensed Matter and Complex Systems,1999,12(4):555-567
[36]W. Aiello, F. Chung, L. Lu.A random graph model for massive graphs.in:Acm,2000.171-180
[37]G. Bianconi, A.L. Barabási.Competition and multiscaling in evolving networks.EPL (EurophysicsLetters),2001,54(436)
[38]R Kumar, J Novak, A Tomkins.Structure and evolution of online social networks.Link Mining: Models,Algorithms, and Applications,2010,337-357
[39]A Mislove,M Marcon,Kp Gummadi et al.Measurement and analysis of online social networks.in:ACM,2007.29-42
[40]A. Mislove,H.S. Koppula,K.P. Gummadi et al.Growth of the flickr social network.in:ACM,2008.25-30
[41]M. Gjoka,M. Kurant,C.T. Butts et al.Practical Recommendations on Crawling Online Social Networks.Selected Areas in Communications, IEEE Journal on,2011,29(9):1872-1892
[42]B. Viswanath,A. Mislove,M. Cha et al.On the evolution of user interaction in facebook.in:ACM,2009.37-42
[43]J.M. Kleinberg.Challenges in mining social network data: processes, privacy, and paradoxes.in:ACM,2007.4-5
[44]M. Fiedler.Algebraic Connectivity of Graphs.Czechoslovak Math. J,1973,23(298-305
[45]A. Pothen, H.D. Simon, K.P. Liou.Partitioning sparse matrices with eigenvectors of graphs.SIAM J.MATRIX ANAL. APPLIC.,1990,11(3):430-452
[46]B.W. Kernighan, S. Lin.An efficient heuristic procedure for partitioning graphs.Bell System TechnicalJournal,1970,49(2):291-307
[47]M. Girvan, M.E.J. Newman.Community structure in social and biological networks.Proceedings of theNational Academy of Sciences,2002,99(12):7821
[48]J.R. Tyler, D.M. Wilkinson, B.A. Huberman.E-mail as spectroscopy: Automated discovery ofcommunity structure within organizations.The Information Society,2005,21(2):143-153
[49]F. Radicchi,C. Castellano,F. Cecconi et al.Defining and identifying communities in networks.Proceedings of the National Academy of Sciences of the United States of America,2004,101(9):2658
[50]H. Tsuchiura,M. Ogata,Y. Tanaka et al.Electronic states around a vortex core in high-T_{c}superconductors based on the tJ model.Physical Review B,2003,68(1):012509
[51]S. Fortunato, V. Latora, M. Marchiori.Method to find community structures based on informationcentrality.Physical review E,2004,70(5):056104
[52]J. Duch, A. Arenas.Community detection in complex networks using extremal optimization.Physicalreview E,2005,72(2):027104
[53]F. Wu, B.A. Huberman.Finding communities in linear time: a physics approach.The European PhysicalJournal B-Condensed Matter and Complex Systems,2004,38(2):331-338
[54]M. Rosvall, C.T. Bergstrom.Maps of random walks on complex networks reveal community structure.Proceedings of the National Academy of Sciences,2008,105(4):1118
[55]L. Donetti, M.A. Munoz.Detecting network communities: a new systematic and efficientalgorithm.Journal of Statistical Mechanics: Theory and Experiment,2004,2004(P10012)
[56]M.E.J. Newman.Fast algorithm for detecting community structure in networks.Physical reviewE,2004,69(6):066133
[57]A. Clauset, M.E.J. Newman, C. Moore.Finding community structure in very large networks.Physicalreview E,2004,70(6):066111
[58]U.N. Raghavan, R. Albert, S. Kumara.Near linear time algorithm to detect community structures inlarge-scale networks.Physical review E,2007,76(3):036106
[59]V.D. Blondel,J.L. Guillaume,R. Lambiotte et al.Fast unfolding of communities in large networks.Journalof Statistical Mechanics: Theory and Experiment,2008,2008(P10008
[60]G. Palla,I. Derényi,I. Farkas et al.Uncovering the overlapping community structure of complex networksin nature and society.Nature,2005,435(7043):814-818
[61]E. Garfield.The history and meaning of the journal impact factor.JAMA: the journal of the AmericanMedical Association,2006,295(1):90
[62]G. Pinski, F. Narin.Citation influence for journal aggregates of scientific publications: Theory, withapplication to the literature of physics.Information Processing&Management,1976,12(5):297-312
[63]J.M. Kleinberg.Authoritative sources in a hyperlinked environment.Journal of the ACM(JACM),1999,46(5):604-632
[64]L. Page,S. Brin,R. Motwani et al.The PageRank citation ranking: Bringing order to the web,1999,
[65]R. Soricut, A. Echihabi.Trustrank: Inducing trust in automatic translations via ranking.in:Associationfor Computational Linguistics,2010.612-621
[66]K. Bharat, G.A. Mihaila.When experts agree: Using non-affiliated experts to rank populartopics.in:ACM,2001.597-602
[67]J. Kincaid.EdgeRank: The secret sauce that makes Facebook’s news feed tick.TechCrunch,2010.
[68]Hamed Haddadi Meeyoung Cha, Fabr′cio Benevenuto,Krishna P. Gummadi.Measuring User Influencein Twitter: The Million Follower Fallacy.International Conference on Weblogs and Social Media,2010,
[69]Ee-Peng Lim Jianshu Weng, Jing Jiang Qi He.TwitterRank Finding Topic-sensitive InfluentialTwitterers.Web Search and Data Mining,2010,
[70]H Kwak,C Lee,H Park et al.What is Twitter, a social network or a news media?in:ACM,2010.591-600
[71]S. Ye, S. Wu.Measuring message propagation and social influence on Twitter. com.SocialInformatics,2010,216-231
[72]A. Goyal, F. Bonchi, L.V.S. Lakshmanan.Learning influence probabilities in social networks.in:ACM,2010.241-250
[73]E. Bakshy,J.M. Hofman,W.A. Mason et al.Everyone's an influencer: quantifying influence ontwitter.in:ACM,2011.65-74
[74]Mit Technology Review.New Algorithm for Measuring the Human Power level,2011,
[75] L. Euler.Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarumPetropolitanae,1741,8(128-140)
[76]C. Bird,A. Gourley,P. Devanbu et al.Mining email social networks.in:ACM,2006.137-143
[77]P.A. Wagstrom, J.D. Herbsleb, K. Carley.A social network approach to free/open source softwaresimulation.in:2005.16-23
[78]K. Crowston, J. Howison.The social structure of free and open source software development.FirstMonday,2005,10(2-7):
[79]L. Zhou,J. Ding,Y. Wang et al.The Social Network Mining of BBS.Journal of networks,2009,4(4):298-305
[80] S.P. Borgatti, M.G. Everett, L.C. Freeman.Ucinet for Windows: Software for social network analysis.Harvard Analytic Technologies,2002,2006
[81]K.I. Goh,Y.H. Eom,H. Jeong et al.Structure and evolution of online social relationships: Heterogeneityin unrestricted discussions.Physical review E,2006,73(6):066123
[82]M.C. Green,J. Hilken,H. Friedman et al.Communication Via Instant Messenger: Short‐and Long‐Term Effects.Journal of Applied Social Psychology,2005,35(3):445-462
[83]A. Miura, K. Yamashita.Psychological and social influences on blog writing: An online survey of blogauthors in Japan.Journal of Computer‐Mediated Communication,2007,12(4):1452-1471
[84]A. Chin, M. Chignell.A social hypertext model for finding community in blogs.in:ACM,2006.11-22
[85]S. Wu,J.M. Hofman,W.A. Mason et al.Who says what to whom on twitter.in:ACM,2011.705-714
[86]B Krishnamurthy, P Gill, M Arlitt.A few chirps about twitter.in:ACM,2008.19-24
[87]L. Backstrom,P. Boldi,M. Rosa et al.Four Degrees of Separation.Arxiv preprint arXiv:1111.4570,2011,
[88]B. Fields,K. Jacobson,C. Rhodes et al.Analysis and Exploitation of Musician Social Networks forRecommendation and Discovery.Ieee Transactions on Multimedia,2011,13(4):674-686
[89]微博API. http://open.weibo.com/
[90] Z. Guo, Z. Li, H. Tu, and D. Xie. Detecting and Modeling the Structure of a Large-Scale Microblog.Springer Lecture Notes in Electrical Engineering (LNEE)-Proceedings of2012International Conference onFuture Information Technology. Vancouver, Canada.
[91]用户统计.http://it.sohu.com/20111109/n325056186.shtml
[92]中华人民共和国国家统计局.2010年第六次全国人口普查主要数据公报.2011.
[93]赵嘉怡.女性撑起社交网站半边天?互联网周刊,2012,7:38-39
[94] Z.Guo, Z.Li, H.Tu and L.Li. Characterizing user behavior in Weibo. The3rd International Conferenceon Mobile, Ubiquitous, and Intelligent Computing.2012,Vancouver, Canada.
[95]孟波.新浪微博:一场正在发生的信息传播变革.南方传媒研究第21辑,南方日报出版社,2009
[96] QQ在线人数.http://im.qq.com/online.shtml#qq
[97]X. Hei,C. Liang,J. Liang et al.A measurement study of a large-scale P2P IPTV system.Multimedia, IEEETransactions on,2007,9(8):1672-1687
[98]10Fascinating Facebook Facts.http://mashable.com/2010/07/22/facebook-facts/
[99]Ba Huberman, Dm Romero, F Wu.Social networks that matter: Twitter under the microscope.FirstMonday,2009,14(1):8
[100] P. Van Mieghem, Performance Analysis of Communications Networks and Systems.Cambridge, U.K.: Cambridge Univ. Press,2006.
[101] R.K. Merton.The Matthew effect in science.science,1968,159(3810):56-63
[102]V. Batagelj, A. Mrvar.Pajek—analysis and visualization of large networks.Graph drawing software,2004,77-103
[103]A. Rapoport.Spread of information through a population with socio-structural bias: I. Assumption oftransitivity.Bulletin of Mathematical Biology,1953,15(4):523-533
[104]R. Guimera, L.A.N. Amaral.Functional cartography of complex metabolic networks.Nature,2005,433(7028):895-900
[105]Y.Y. Ahn, J.P. Bagrow, S. Lehmann.Link communities reveal multiscale complexity in networks.Nature,2010,466(7307):761-764
[106]S. Fortunato, M. Barthelemy.Resolution limit in community detection.Proceedings of the NationalAcademy of Sciences,2007,104(1):36
[107]Lynn Smith-Lovin Miller Mcpherson, And, James M Cook.Birds of a feather Homophily in socialnetworks,2001,
[108] J. Paul.(1901),étude comparative de la distribution florale dans une portion des Alpes et des Jura,Bulletin de la SociétéVaudoise des Sciences Naturelles37:547–579.
[109]M. E. J. Newman, M. Girvan.Finding and evaluating community structure in networks.Physicalreview E,2004,69(2):
[110]W.W. Zachary.An information flow model for conflict and fission in small groups.Journal ofanthropological research,1977,452-473
[111]D. Lusseau, M.E.J. Newman.Identifying the role that animals play in their social networks.Proceedingsof the Royal Society of London. Series B: Biological Sciences,2004,271(Suppl6):S477-S481
[112]A. Lancichinetti, S. Fortunato, F. Radicchi.Benchmark graphs for testing community detectionalgorithms.Physical review E,2008,78(4):046110
[113]L. Danon,A. Díaz-Guilera,J. Duch et al.Comparing community structure identification.Journal ofStatistical Mechanics: Theory and Experiment,2005,2005(P09008)
[114]Z. Guo, Z. Li, H. Tu.Sina Microblog: An Information-Driven Online Social Network. in:IEEE,2011.160-167
[115]A.N. Langville, C.D. Meyer, P. Fern ndez.Google’s pagerank and beyond: The science of searchengine rankings.The Mathematical Intelligencer,2008,30(1):68-69
[116]X. Li, G. Chen.A local-world evolving network model.Physica A: Statistical Mechanics and itsApplications,2003,328(1):274-286
[117]P. Chen,H. Xie,S. Maslovet al.Finding scientific gems with Google’s PageRank algorithm.Journal ofInformetrics,2007,1(1):8-15