社会网络分析本科毕业论文

1、        点：行动者、节点（actors, nodes）

即为社会网络中的一个功能个体（包括个人、单位、团体（看成一个整体）），在虚拟网络中表现为一个注册用户，ID等。

在社会网络研究领域，任何一个社会单位、社会实体或功能个体都可以看成是“节点”，或者行动者。

一个图中： 节点集合N={n1,n2,、、、n3}

2、        线,关系（relationship）：

用来刻画关系数据，关于接触、联络、关联、群体依附和聚会等方面的数据，这类数据把一个能动者与另外一个能动者联系在一起，因而不能还原为单个行动者本身的属性。如上图表示的线arc。

一般称由一条线连着的点是相互“邻接的（adjacent）”,邻接是对由两个点代表的两个行动者之间直接相关这个事实的图论表达。

一般有无向线、有向线、多值线、有向多值线。

由线构成的图无向图、有向图、有向多值、无向多值图。

3、        邻域（neighborhood）:

与某个特定点相邻的那些点成为该点的“邻域”。

4、        度数（degree）:

邻域中的总点数成为度数。（严格的说应该是“关联度”，（degree of connection））,一个点的度数就是对其“邻域”规模大小的一种数值侧度。

一个点（无向图）的度数，在邻接矩阵中，一个点的度数用该点所对应的行或者列的各项中的非0值总数来表示。如果是二值（有项）的，那么一个点的度数就是该点所在行和所在列的总合。

在有向图中，“度数”包括两个不同方面，表达社会关系的线的方向。分别称为“点入度（in-degree）”：直接指向该点的点数总合；和“点出度（out-degree）”：该点所直接指向的其它点的总数。因此，对应在有向图的矩阵上，点的入度：对应该点所在列的地总和上。出度：该点所在行的总和上。

所有点的度数总合：无向图的总度数查线（关系）即可，有项图的总度数查线的2倍。

5、        线路（walk）：

各个点可以通过一条线直接相连，也可以通过一系列线间接相连，在一个图中的这一系列线叫做一条“线路”。

6、        途经(path)：

线路中每个点和每条线都各不相同，则称该线路为“途经”，“途经”的“长度”，用构成该途经的线的条数来测量。

7、        距离(distance):

一个重要的概念，指连接两个点的最短路径（即捷径，geodesic）的长度。在图论中一般称作最短路经。要与“途经”的概念相区分。

8、        方向

主要是看有向图的方向问题。

9、        密度（density）

描述了一个图中各个点之间关联的紧密程度。一个“完备(complete)图”（在图论中称完全图）指的是一个所有点之间都相互邻接的图。这种完备性即使在小网络中也积极少见。密度这个概念试图对线的总分布进行汇总，以便测量图在多大程度上具有这种完备性。密度依赖于另外两个网络结构参数：图的内含度和图中各点的度数总和。密度指的是一个图的凝聚力的总体水平。

“密度”和“中心势”这两个概念代表的是一个图的总体“紧凑性（compactness）”的不同方面。

图的内含度（inclusiveness）：图中各类关联部分包含的总点数，也可表述为图的总点数减去孤立点的数。不同的图进行比较常用的侧度为： 关联点数/总点数 15/20=75%

各点度数总和：

密度计算公式： 图中实际拥有的连线数与最多可能拥有的线数之比，其表达式为2l/n(n-1)。  有向图的表达式为：l/n(n-1)

多值图的密度：需要估值多重度问题，显然多重度高的线对于网络密度的贡献要比多重度低的线的贡献大。比较有争议的一种测度。

巴恩斯（Barnes,1974）比较了两类社会网络分析：

10、        个体中心（ego-centric） 网研究

围绕特定的参考点而展开的社会网，密度分析关注的是围绕着某些特定行动者的关系的密度。计算个体中心网密度的时候，通常不考虑核心成员及与该成员有直接关系的接触者，而是只关注在这些接触者之间存在的各种联系（links）。

11、        社会中心（socio-centric）网研究

关注的是作为一个整体的网络关联模式，这是对社会网络分析的另外一类贡献，从这一角度出发，密度则不再是局部行动者的“个体网”密度，而是整个网络的密度。密度计算上文已经提到。

12、        点度中心度（point centrality）

一个图中各个点的相对中心度

13、        图的中心度（graph centrality） 即为中心势的概念

14、        整体中心度（global centrality）   （弗里曼Freeman 1979,1980）

整体中心度指的是该点在总体网络中的战略重要性。根据各个点之间的接近性（closeness）,根据不同点之间的距离。可以计算出图中某点与其他各个点之间的最短距离之和。

无向图：可以通过软件计算出来一个无向图中各个点之间的距离矩阵，那么一个点的“距离和”比较低的点与其他很多点都“接近”。接近性和距离和呈反向关系。

有向图：“内接近性（in-closeness）”和“外接近性(out-closeness)”来计算

15、        局部中心点

一个点在七紧邻的环境中与很多点有关联，如果一个点有许多直接相关的“邻点”，我们便说该点是局部中心点。

16、        整体中心点

如果一个点在网络的总体结构上占据战略上的重要地位，我们就说该点是整体中心点。

17、        局部中心度（local centrality）

局部某点对其邻点而言的相对重要性。测量仅仅根据与该点直接相连的点数，忽略间接相连的点数。在有向图中有内中心度（in-centrality）和外中心度（out-centrality）。也可以自定义距离为1或2进行测度，如果定义为4（大多数点的距离为4），就毫无意义，也没有信息。

18、        局部中心度的相对测度

点的实际度数与可能联络得最多度数之，注意要去掉该点本身。

19、        中心势（centralization） 弗里曼(freeman，1979)

指的不是点的相对重要性，而是整个图的总体凝聚力或整合度。很少有人试图界定一个图的结构中心思想。中心势描述的则是这种内聚性能够在多大程度上围绕某些特定点组织起来。因此，中心势和密度是两个重要的、彼此相互补充的量度。

核心点的中心度和其它点的中心度之差。因此得出概念：实际的差值总和和与最大可能的差值总和相比。

社会网络分析理论： 在社会网络[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.