基于社会网络的社区发现和中心性分析算法研究

发布时间：2017-01-05 08:20

第 1 章 绪 论

1.1 研究背景及意义
在现实世界中，社会网络更是被广泛应用于各领域，如科技、商业、经济和生物领域，包括电力网络、电话交互图、计算机病毒传播、万维网以及科学家的合作关系和引用网络；生物学网络，流行病学网络、细胞新陈代谢网络和食物网络到线虫类和蠕虫的神经网络；公司内部的 E-mail 信息交换、新闻组、聊天室、朋友关系以及典型的“老小孩”网络等。而真实的社会网络非常庞大，广大用户作为内容、信息的生产者的同时也承担了消费者的角色。社会网络是由个体之间信息交互、作用联系而形成的相对稳定的关系体系。通过对数百万甚至数以亿计的用户产生的海量数据进行大规模的社会网络分析，可以有效应用于社区发现、中心性分析、数据分类、兴趣推荐及垃圾信息处理等方面的研究，为研究人员分析、观测、挖掘信息提供有利的条件，为人类的行为研究提供新的机会。

社区又称为群组、簇或者模块，集合内部节点间有非常强烈的作用，而集合外部节点则可能有比较弱的作用关系或者无作用关系。社区发现可以反映出社会网络的真实拓扑结构，可以被应用于许多领域，如在生物学方面，可以依据蛋白质的功效，将功效上作用相同的蛋白质划分为同一个社区，从而为医学领域的研究提供有利的支持；在万维网研究方面，通过社区发现将主题相同或内容相关的网页进行划分，使网页信息搜索者更加快速地定位所需信息；在并行计算方面，需要将处理器之间的信息交换最大程度的最小化实现，采用图分割的方法对处理器进行任务分配，将计算机分成数目大致相同的组；对于规模巨大的图进行不同社区的划分，可以生成具有更高效率的存储表，进行目的地的路径搜索和地理导航[1]；在中心性分析方面，能通过节点的位置信息对节点是中心节点还是边界节点进行角色判断，一般认为中心节点与其他节点有更多的作用关系，处于重要程度较高位置，边界节点主要起到维护社区间关系，进行社区间信息传播、交换的作用。此外对于社区发现的研究在舆情分析、识别暴恐事件、知识发现、链接预测方面也有非常重要的意义。图 1.1 为一个包含三个社区的简单社会网络，社区内部节点间具有较强的联系，边界节点间则具有较弱的联系。

......

1.2 研究现状
1.2.1 社区发现研究现状
社区发现有助于其他社会计算任务的实现，通过对大规模网络进行压缩处理，使得许多实际问题可以在群组级而不是节点级完成求解，这为网络分析提供了直观的解决方法。对于社区发现的研究最早起源于解决图分割问题，早在 20 世纪 70 年代，就提出了 K-L[5]算法，该算法主要采用贪婪策略，对模块函数进行不断的优化，通过改变边数值，使得每次迭代过程生成两个大小已知的社区；Suaris 和 Kedem[6]针对 K-L 算法只能对两个已知社区规模的网络进行划分的缺点，对算法进行了改进，使其可以对任意数量的社区进行计算，但是却增大了时间复杂度的开销；谱平分法[7]是另一种经典的图分割算法，该法基于 Laplace 矩阵，认为同一社区节点对应值几乎相等，但该方法需要进行大量矩阵特征向量的计算，具有较大时间复杂度；“随机游走”[8]概念被引入社区发现研究后，对于无权和加权网络可以更好的进行分析研究，其主要思想为，“随机漫步者”在一个社区内部可以进行长时间游走，因为一个社区具有高度的连通性，故其可在较短距离内到达社区内其他节点，此特征可以被用于相似度的计算；以 k-means 为聚类方法的社区发现算法[9]也广泛用于研究中，该方法选取最初的初始节点，通过与中心节点进行相似度的计算来聚类，形成不同的社区。

现代社区发现算法主要有分裂聚类、凝聚聚类、模块度最大化聚类等方法。Girvan 和 Newman 于 2002 年提出了具有开创性意义的 GN 算法[10]，该算法通过迭代的对具有最大介数值的边进行删除操作，将待划分社区的网络逐步划分为层次结构。之后很多学者对 GN 算法进行了改进，Fast Newman 算法[11]对 GN 算法在性能上进行了改进，Radicchi 提出了使用边聚类系数的 Self-Contained GN 算法[12]；Fortunato 等人提出了信息中心性的概念，即经过从图中移除某节点及与此节点相连接的边后，引起图效率的相对衰退[13]；Newman[14]于 2004 年提出了以模块度作为衡量算法优化条件的算法，其本质是一种贪心算法，直到达到模块度最大时，所划分的社区即为最佳社区；以模块度函数作为优化条件的方法逐渐出现，Guimerà和 Ameral[15]将模拟退火方法首次应用于社区发现中，通过不断的优化模块度函数寻找最优解；Duch 和 Arenas 则提出极值优化方法[16]，通过优化模块度函数，节点进行转移达到最终稳定状态；Blonde 等提出的多层次贪心合并算法[17]是目前既具有最快的执行速度，同时也具有较高准确率的算法之一。

......

第 2 章 社区发现与中心性分析

2.1 社会网络

通常有两种方法表示一个网络，一种是基于图的方法，此法为直观的方法；还有一种是基于矩阵的方法，该矩阵也称为邻接矩阵。人们常将社会网络建模成图论的形式进行研究，将个体抽象成代表个人或者组织的节点，将个体之间的联系抽象成边。而真实的网络，可以是加权的、有符号的、有向的网络。在加权网络中，每条边都是与数值相关联的；在有符号网络中，一些边是正联系，另一些边则代表负联系；在有向网络中，边的指向一般是有方向的，并且是不对称的。图 2.1 为老鼠体内癌细胞中蛋白质网络，不同颜色簇代表了不同的社区结构，社区的结构与癌变及疾病的转移有密切关系[25]。

......

2.2 社会网络的特征
2.2.1 小世界效应
在真实社会生活中，两个陌生人可以通过相互熟识的人间接的联系起来，反映了“小世界”的概念，1967 年，哈佛大学的社会学家 Stanley Milgram 和他的同事进行实验，要求堪萨斯州和内布拉斯加州的人们给住在波斯顿的陌生人写信，并将信转寄给他们认为可能认识这些陌生人的朋友。通过不超过 5 个中间人，一半的信成功到达，Milgram 和其他人在其他城市之间进一步研究表明，世界上任何两个个体之间看起来似乎存在着普遍的“六度分割”。这个结果同时也被一个巨大的即时信息网络所证实，这个网络包含 1800 万用户，而任意两个人之间的距离是 6.6[26]。从现实的大规模网络中，都可以观察到一个小直径。
2.2.2 稠化幂率
早期人们认为直径作为网络规模的函数缓慢增加，然而有效直径是趋向于随网络增长而减小的。将引用网络作为一个直观的例子，其中网络中的节点表示一篇论文，而有向边表示一篇论文 v 引用了另外的论文 w。当 v 引用 w 时，w 便被“冻结”了，以后其它论文 q 则直接引用 v，从而缩短了网络内节点之间的距离。

网络中存在大量节点，节点的重要程度是不同的，通常认为处于较高职位或具有更大的影响力的人在网络中处于重要的位置，社会网络分析中用“中心性”来描述节点的重要程度。具有较高中心性的节点在网络中会扮演重要角色，若将其移出网络，则会对网络产生不可估量的影响，甚至会导致网络的瘫痪。计算中心性的方法主要有度中心性、特征向量中心性、紧密度中心性[2]等。通过计算中心性，可以对网络中节点进行重要度排序，挖掘关键节点、社区发现等。

......

第 3 章 基于排序中心性的社区发现算法.............................16
3.1 PAM 聚类算法...............................................16
3.2 基于排序中心性的社区发现算法(RCCD).......................... 16
第 4 章 基于主观贝叶斯的中心性分析算法............................30
4.1 主观贝叶斯方法简介.............................................30
4.2 基于主观贝叶斯的中心性分析算法..................................31
第 5 章 总结与展望....................................................36
5.1 论文总结....................................................36

5.2 工作展望........................................................36

第 4 章 基于主观贝叶斯的中心性分析算法

社会网络中有很多种度量中心性的方法，但大多数方法都是从某单一角度对网络内节点的重要程度进行评估，所以本章提出了一种基于主观贝叶斯的中心性分析算法，即 CAB 算法。本章首先对主观贝叶斯方法进行了简要介绍，然后对实现 CAB 算法需要的相关理论知识及算法步骤进行了详细分析。算法结合传统的度量方法，构建了包含 3 种方法的证据指标集合，通过主观贝叶斯方法对不确定性证据指标进行合成，最终得出准确率较高的中心性排名。

4.1 主观贝叶斯方法简介
由分析可发现本文所提 CAB 算法得到结果排名靠前的节点大多与单独使用度、紧密度、介数进行排名靠前的节点相同，也从侧面验证了本文算法的正确性。从表数据可以看出，有的节点具有相同的度，有的节点紧密度相同，从而无法进行下一步区分，判断出节点间的相对重要程度，使用 CAB 算法得到排名最靠前的 3 个节点为 34，1，33 号节点，，在第三章社区发现的算法中得到 34，1 号节点分别是两个社区的中心节点，而 33 号节点在社区 2 中也占有很高的地位，9 号和 14 号节点具有相同的度数和紧密度，但是从 3.4.1 节社区划分的结果上看，9号节点与另外一个社区的节点连接较多，所以其中心性更高，所以也从侧面验证了本文算法的有效性。本文所提算法从多方面考虑，综合几种指标对社会网络的影响，更好的进行了中心性排名。

由分析表可知，各球队间比赛次数大致相同，所以度数相差不多，此种情况下无法按照度中心性对网络内节点进行中心性排名，使用本文提出的 CAB 算法对网络节点进行中心性分析，从结果中可以发现，中心性较高的节点大多为 3.4.2节社区划分得到的社区的中心节点，且多数都为介数、紧密度较高节点，从侧面验证了本文所提算法的正确性，而 CAB 算法又充分结合了多个指标，综合对其进行合成，得出的结果更全面，也更具现实意义。

......

第 5 章 总结与展望

5.1 论文总结
首先本文基于 PAM 聚类算法的启发，提出了基于排序中心性的社区发现算法 RCCD。算法首先在初始种子节点选取时，采用离心率中心性分析方法对节点进行排名，选取排名靠前且使用阈值  作为约束的 k 个节点作为初始节点集，以使节点间距离尽量远并且分散，来提高初始中心节点选取的准确率。然后使用Cosine 方法计算节点间相似度，使节点根据相似度原则划分入各社区，再依据PAM 聚类算法思想，依据代价函数进行代表对象（中心节点）的替换，在替换时，采取在各社区利用离心率中心性对节点进行排名并形成中心节点候选集，从中心节点候选集选取节点进行替换的策略，来更新中心节点，直到中心节点不再变化或者社区结构不再变化，算法终止。

使用 RCCD 算法在空手道和橄榄球队数据集上进行实验验证，得到了很好的社区划分，并且产生了很好的纯度和模块度值，在一定程度上，较以往算法也有一定提高。其次提出了基于主观贝叶斯的中心性分析算法（CAB 算法），该算法选取了传统的用于度量社会网络中心性的度中心性、介数中心性、离心率中心性 3 种方法，用于构建不确定性证据合成的指标集，最后结合主观贝叶斯方法进行合成。本文算法在空手道和橄榄球队数据集上对 CAB 算法进行了实验，由于这两个数据集均没有给出网络内节点真实的排名顺序，所以采用与度中心性、介数中心性、紧密度中心性三个指标进行对比实验的方法来验证本文算法的正确性。CAB 算法不同于以往的中心性分析方法，以往的方法都是针对单一指标单独的对网络中心性进行度量，而 CAB 算法综合各指标，且利用了主观贝叶斯方法可以对不确定证据进行处理的优点，可以更全面的进行社会网络中心性排名。

......

参考文献（略）

本文编号：234644