社会网络分析理论：

在社会网络[63]由人类学家Barnes最早提出的概念，他在社会网络的分析基础上统地研究挪威一个小渔村的跨亲缘与阶级的关系。在社会网络分析中，存在一些经典的理论。这些理论主要包括:六度分割理论、弱关系理论、150法则、小世界网络理论、马太效应等。基于社会网络有关的研究方向和内容，在不同的领域着发挥着各自的作用，例如，社会影响力分析，社区发现，信息传播模型，链接预测，基于社会网络的推荐。

150法则是指一个人能保持稳定社交关系的人数上限通常为150人。1929年由英国罗宾•邓巴教授(Robin Dunbar)提出了经典的”150定律”理论，该定律同时也被称为“邓巴数字”[64]。这个定律在我们的实际日常生活中的应用是相当普遍的，SIM卡中只能存储150个联系人的电话，微软的MSN中也只可以最多把150位联系人的信息添加到自己的名单中[64]等等。

小世界网络是一种具有特殊结构的复杂网络，在这种网络中大部份的节点是不相邻的，但绝大部份节点之间是连通的且距离很短。六度分割理论也是小世界网络理论的一种体现。在多数现实世界的社会网络中，尽管网络中的节点数量巨大，网络中相邻的节点相对较少，但每两个节点间往往只需要很短的距离便能连通。

六度分割就是指一个人与其他任何一个人之间建立起联系，最多都只需要经过六个人。所以，即便邓巴数字告诉我们，我们是能力上维持一个特别大的社交圈的，但是六度分割理论却可以告诉我们，通过我们现有的社交人脉圈以及网络可以无限扩张我们的人脉圈，在需要的时候都能够和地球中想要联系的任何人取得联系。

弱关系理论弱关系(Weak Tie)是指需要较少或不需要情感联系的人们之间的社会联系，这种联系几乎不需要耗费个人的时间或精力来维系，但这种联系却很有作用。美国社会学家Mark Granovetter在研宄人们在求职过程中如何获取工作信息时发现[65]，由家人、好友等构成的强关系在获取工作信息过程中起到的作用很有限，而那些关系较疏远的同学、前同事等反而能够提供更加有用的求职信息。

马太效应可以理解为达尔文进化论中适者生存的理念。在社交网络的发展过程如同生物进化的过程，存在强者越强、弱者越弱的现象。也就是说，在社交网络中越是处于网络核心的节点很大可能会变来越核心，而那些处于社交网络中边缘地带的节点或许会越来越不重要甚至直至消失。那些在社交网络中相比其他节点拥有更大影响力的节点，其带给该网络的影响也要比那些拥有弱影响力的节点所带来的影响要强。

从不同角度探索节点影响力挖掘算法：

1.基于邻节点中心性的方法。这类方法最简单最直观，它根据节点在网络中的位置来评估节点的影响力。度中心性[13]考察网络中节点的直接邻居数目，半局部中心性[14]考察网络中节点四层邻居的信息，ClusterRank[15]同时考虑了网络中节点的度和聚类系数。

2.基于路径中心性的方法。这类方法考察了节点在控制信息流方面的能力，并刻画节点的重要性。这类方法包括子图中心性[16]、数中心性[17]（一些演化算法包括：路由介数中心性[18]，流介数中心性[19]，连通介数中心性[20]，随机游走介数中心性[21]等）及其他基于路径的挖掘方法。

3.迭代寻优排序方法。这类方法不仅考虑了网络中节点邻居的数量，并且考虑邻居质量对节点重要性的影响，包括了特征向量中心性[13]，累积提名[22]，PageRank算法[23]及其变种[24-32]。

4.基于节点位置的排序算法。这类方法最显著的特点是，算法并没有给出一个计算节点重要性的定义，而是通过确定节点在网络中的位置，以此来确定节点的重要程度。在网络核心位置的节点，其重要性就相对较高，相反的，若节点处于网络边缘，那么它的重要性就会比较低。基于节点位置的以及不同应用场景的推荐算法具有重要的研究意义[34-37]。

节点影响力评估方法：

在社交网络节点影响力的评估方法主要可以分为三类，基于静态统计量的评估方法、基于链接分析算法的评估方法，基于概率模型的评估方法。

众学者在静态统计量的方法上，结合不同社交网络中相关信息，借鉴链接分析法以及建立概率模型来评估节点影响力，对社交网络节点影响力可以做到更有效的评估[66]。

1)基于静态统计量度量方法

主要是通过网络中节点的一些静态属性特征来简单直接地体现节点的影响力，但面对社交网络中复杂信息以及不同平台，并不能有效地度量不同社交网络中节点影响力。如度中心性，主观认为节点的重要性取决于与其他节点连接数决定，即认为一个节点的邻居节点越多，影响力越大。在有向网络中，根据边的方向，分为入度和出度，在有权网络中，节点的度可以看作强度，即边的权重之和。度中心性刻画了节点的直接影响力，度中心性指标的特点是简单、直观、计算复杂度低，也具有一定合理性。

但针对不同平台的网络结构中，度中心性的影响力效果未必能达到目标效果，而且社交网络中用户间关系的建立具有一定的偶然性，而且不同的用户间的关系强度也不同。度中心性没有考虑了节点的最局部信息，虽然对影响力进行了直接描述，但是没有考虑周围节点处所位置以及更高阶邻居。众学者在静态统计量的方法上，结合不同社交网络中相关信息，借鉴链接分析法以及建立概率模型来评估节点影响力，对社交网络节点影响力可以做到更有效的评估[66-67]。

2)基于链接分析算法的方法

链接分析算法(Link Analysis)主要应用在万维网中用来评估网页的流行性。通过超链接，万维网中的网页连接成一个网络，同时这个网络也具备了小世界网络的特征，且微博平台中的关注和粉丝关系与网页的链入与链出十分相似，因此链接分析法的思想也被应用在了微博社交网络中节点影响力的评估中。经典的算法是PageRank[68]和HITS算法[69](Hyperlink-Induced Topic Search)。

PageRank算法模型，是Google在搜索引擎结果中对网站排名的核心算法，核心思想通过计算页面链接的数量和质量，来确定网站的重要性的粗略估计，即节点的得分取决于指向它的节点的数量和这些节点的本身得分。即有越多的优质节点指向某节点时它的得分越高。

HITS算法是由Jon Kleinberg于1997年提出的。HITS算法模型中，有两类节点，权威(Authority)节点，和枢纽(Hub)节点。权威节点在网络中具有高权威性，枢纽节点具有很个指向边的节点。通过计算网络中每个节点的Authority权威值和Hub枢纽值来寻找高权威性的节点。即求值过程是在迭代中计算Authority和Hub值，直到收敛状态。Hub值和Authority值计算公式。

通过多数研究者发现，将链接分析法结合社交网络特性可以更好的对用户影响力进行评估，由于技术的快速发展，社交网络的多变性，因此如何将社交网络中的复杂数据和用户行为与相关算法进行结合，仍是需要我们继续研究的方向。

3)基于概率模型的方法

主要是建立概率模型对节点影响力进行预测。这么多学者将用户影响力作为参数对社交网络中的节点用户行为建立概率模型，并根据社交网络中已有的用户数据求解概率模型，得出用户影响力。

文献[70]认为用户间影响力越大、被影响用户的活跃度和转发意愿越高，则其转发另一个用户的信息的概率越大，所以利用用户影响力、转发意愿和活跃度等构建转发概率模型。通过用户发布的tweet数量、转发的tweet数和用户的历史转发行为数据，计算出用户活跃度、转发意愿和转发概率，进而社交网络中用户影响力。

文献[71]在度量影响力时融合了用户发布信息的主题生成过程，认为兴趣相似或经常联系的用户间影响力较强，用户的行为受其朋友的影响也受其个人兴趣的影响。基于这些假设，结合文本信息和网络结构对LDA模型进行扩展，在用户发布信息的基础上建立模型，通过解模型计算得出用户间基于主题的影响力。

文献[72]认为转发概率同样可以体现用户间的影响力，根据用户间的关注关系。历史转发记录，利用贝叶斯模型预测用户间的转发概率。

文献[73]考虑了用户建立关注关系的原因，用户被关注可能是与关注者兴趣投，也可能受用户的影响力影响。将基于用户的主题建模和基于主题的影响力评估相结合，并在同一个生成模型中进行计算，提出基于LDA算法模型的扩展算法模型FLDA模型(Followship-LDA)。

[13] P. Bonacich. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972, 2(1): 113-120

[14]D.Chen,L.Lü,M.S.Shang,etal.Identifyinginfluentialnodesincomplexnetworks[J]. Physica A, 2012, 391(4): 1777-1787

[15] D. B. Chen, H. Gao, L. Lü, et al. Identifying influential nodes in large-scale directed networks: The role of clustering[J]. PLoS One, 2013, 8(10): e77455

[16]E.Estrada, J.A. Rodriguez-Velazquez.Subgraphcentralityincomplexnetworks[J].Physical Review E, 2005, 71(5): 122-133

[17]L.C.Freeman.Asetofmeasuresofcentralitybasedonbetweenness[J].Sociometry,1977, 40(1): 35-41

[18] S. Dolev, Y. Elovici, R. Puzis. Routing betweenness centrality[J].Journal of the ACM, 2010, 57(4): 710-710

[19] Y. Gang,Z.Tao, H. Bo,etal. Efficientroutingoncomplexnetworks[J].PhysicalReviewE, 2005, 73(4): 46108

[20] E. Estrada, D. J. Higham, N. Hatano. Communicability betweenness in complex networks[J]. Physica A, 2009, 388(5): 764-774

[21]M.E.J.Newman.Ameasureofbetweennesscentralitybasedonrandomwalks[J].Social networks, 2005, 27(1): 39-54

[22]R.Poulin,M.C.Boily,B.R.Masse.Dynamicalsystemstodefinecentralityinsocial networks[J]. Social networks, 2000, 22(3): 187-200

[23] B. S. Brin, L. Page. The anatomy of a large scale hypertextual Web search engine[J]. Computer Networks & ISDN Systems, 1998, 30: 107-117

[24] P. Jomsri, S. Sanguansintukul, W. Choochaiwattana. CiteRank: combination similarity and static ranking with research paper searching[J]. International Journal of Internet Technology & Secured Transactions, 2011, 3(2): 161-177

[13][25]H.S.Bhat,B.Sims.InvestorRankandanInverseProblemforPageRank[D].California: University of California. 2012

[26] J. Weng, E. P. Lim, J. Jiang, et al. Twitterrank: finding topic-sensitive influential twitterers[C]. Third International Conference on Web Search & Web Data Mining, ACM, 2010, 261-270

[27]Y.B.Zhou,L.Lu,M.Li.Quantifyingtheinfluenceofscientistsandtheirpublications: distinguishingbetweenprestigeandpopularity[J].NewJournalofPhysics,2012,14(14): 33033-33049

[28] J. Xuan, H. Jiang, Z.Ren, et al. Developer prioritization in bug repositories[C]. International Conference on Software Engineering, 2012, 25-35

[29]Q.Li,T.Zhou,L.Lü,etal.IdentifyingInfluentialSpreadersbyWeightedLeaderRank[J]. Physica A, 2013, 404(24)47-55

[30] L. Lü, Y. C. Zhang, C H Yeung, et al.Leaders in social networks, the delicious case[J]. PLoS One, 2011, 6(6): e21202

[31]J.M.Kleinberg.Authoritativesourcesinahyperlinkedenvironment[J].Authoritative sources in a hyperlinked environmen, 1999, 46(5): 604-632

[32]R.Lempel,S.Moran.Thestochasticapproachforlink-structureanalysis(SALSA)andthe TKC effect[J]. Computer Networks, 2000, 33(2): 387-401

[33]T.Martin,X.Zhang,M.E.J.Newman.Localizationandcentralityinnetworks[J].Physical Review E, 2014, 90(5): 052808

[34] A. Banerjee, A. G. Chandrasekhar, E. Duflo, et al. Gossip: Identifying central individuals in a social network[R]. National Bureau of Economic Research, 2014.

[35]S.Ji,L.Lu,C.H.Yeung,etal.Effectivespreadingfrommultipleleadersidentifiedby percolation in social networks[J]. arXiv preprint arXiv:1508.04294, 2015.

[36] S. Y. Tan, J. Wu, L. Lü, et al. Efficient network disintegration under incomplete information: the comic effect of link prediction[J]. Scientific Reports, 2016, 6.

[37]任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通报, 2014,59(13): 1175-1197

[63]贝克,晓冬.社会资本制胜:如何挖掘个人与企业网络中的隐性资源[M].上海交通大学出版社,2002.

[64]天涯.六度分隔理论和150法则[EB/OL].http://blog.sina.com.cn/s/blog_62bae1640100|5f3.html.[2010-07-14].

[65]Granovetter M S.The Strength of Weak Ties[J]. American journal of sociology, 1973: 1360-1380.

[66]王梓.社交网络中节点影响力评估算法研究[D].北京邮电大学, 2014.

[67] Meeyoung Cha, Hamed Haddadi,Fabricio Benevenutoets. Measuring User Influence in Twitter: The Million Follower Fallacy[C]. Proceedings of the 4th International AAAI Conference on Weblogs and Social Media (ICWSM),2010:10-17

[3][68]  Page, Lawrence, Brin, et al. The PageRank citation ranking[C]// BringingOrder to the Web. Stanford InfoLab. 1998: 1-14.

[4][69]Kleinberg J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM, 1999, 46(5): 604-632.

[70]Zibin Yin, Ya Zhang. Measuring Pair-Wise Social Influence inMicroblog[C], 2012 ASE/IEEE International Conference on SocialComputing and 2012 ASE/IEEE International Conference on Privacy,Security, Risk and Trust, 2012: 502-507.

[71]Lu Liu, Jie Tang, Jiawei Han, Meng Jiang, Shiqiang Yang. Mining topic-level influence in heterogeneous networks[C]. Proceedings of the 19th ACMinternational conference on information and knowledge management, 2010: 199-208.

[72] Qianni Deng, Yunjing Dai. How Your Friends Influence You: Quantifying Pairwise Influences on Twitter[C], International Conference on Cloud and Service Computing, 2012:185-192.

[73] Bi, Bin, et al. Scalable Topic-Specific Influence Analysis on Microblogs[C], Proceedings of the 7th ACM international conference on Web search and data mining,2014: 513-522.