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

《基于社会网络的社区发现和中心性分析算法研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基于社会网络的社区发现和中心性分析算法研究-->第1章绪论1.1研究背景及意义在现实世界中，社会网络更是被广泛应用于各领域，如科技、商业、经济和生物领域，包括电力网络、交互图、计算机病毒传播、万维网以及科学家的合作关系和引用网络；生物学网络，流行病学网络、细胞新陈代谢网络和食物网络到线虫类和蠕虫的神经网络；公司内部的E-mail信息交换、新闻组、聊天室、朋友关系以及典型的“老小孩”网络等。而真实的社会网络非常庞大，广大用户作为内容、信息的生产者的同时也承担了消费者的角色。社会网络是由个体之间信息交互、作用联系而形成的相对稳定的关系体系。通过对

2、数百万甚至数以亿计的用户产生的海量数据进行大规模的社会网络分析，可以有效应用于社区发现、中心性分析、数据分类、兴趣推荐及垃圾信息处理等方面的研究，为研究人员分析、观测、挖掘信息提供有利的条件，为人类的行为研究提供新的机会。社区又称为群组、簇或者模块，集合内部节点间有非常强烈的作用，而集合外部节点则可能有比较弱的作用关系或者无作用关系。社区发现可以反映出社会网络的真实拓扑结构，可以被应用于许多领域，如在生物学方面，可以依据蛋白质的功效，将功效上作用相同的蛋白质划分为同一个社区，从而为医学领域的研究提供有利的支持；在万维网研究方面，通过社区发现将

3、主题相同或内容相关的网页进行划分，使网页信息搜索者更加快速地定位所需信息；在并行计算方面，需要将处理器之间的信息交换最大程度的最小化实现，采用图分割的方法对处理器进行任务分配，将计算机分成数目大致相同的组；对于规模巨大的图进行不同社区的划分，可以生成具有更高效率的存储表，进行目的地的路径搜索和地理导航[1]；在中心性分析方面，能通过节点的位置信息对节点是中心节点还是边界节点进行角色判断，一般认为中心节点与其他节点有更多的作用关系，处于重要程度较高位置，边界节点主要起到维护社区间关系，进行社区间信息传播、交换的作用。此外对于社区发现的研究在舆情

4、分析、识别暴恐事件、知识发现、链接预测方面也有非常重要的意义。图1.1为一个包含三个社区的简单社会网络，社区内部节点间具有较强的联系，边界节点间则具有较弱的联系。......1.2研究现状1.2.1社区发现研究现状社区发现有助于其他社会计算任务的实现，通过对大规模网络进行压缩处理，使得许多实际问题可以在群组级而不是节点级完成求解，这为网络分析提供了直观的解决方法。对于社区发现的研究最早起源于解决图分割问题，早在20世纪70年代，就提出了K-L[5]算法，该算法主要采用贪婪策略，对模块函数进行不断的优化，通过改变边数值，使得每次迭代过程生成两个

5、大小已知的社区；Suaris和Kedem[6]针对K-L算法只能对两个已知社区规模的网络进行划分的缺点，对算法进行了改进，使其可以对任意数量的社区进行计算，但是却增大了时间复杂度的开销；谱平分法[7]是另一种经典的图分割算法，该法基于Laplace矩阵，认为同一社区节点对应值几乎相等，但该方法需要进行大量矩阵特征向量的计算，具有较大时间复杂度；“随机游走”[8]概念被引入社区发现研究后，对于无权和加权网络可以更好的进行分析研究，其主要思想为，“随机漫步者”在一个社区内部可以进行长时间游走，因为一个社区具有高度的连通性，故其可在较短距离内到达社

6、区内其他节点，此特征可以被用于相似度的计算；以k-means为聚类方法的社区发现算法[9]也广泛用于研究中，该方法选取最初的初始节点，通过与中心节点进行相似度的计算来聚类，形成不同的社区。现代社区发现算法主要有分裂聚类、凝聚聚类、模块度最大化聚类等方法。Girvan和Nean于2002年提出了具有开创性意义的GN算法[10]，该算法通过迭代的对具有最大介数值的边进行删除操作，将待划分社区的网络逐步划分为层次结构。之后很多学者对GN算法进行了改进，FastNean算法[11]对GN算法在性能上进行了改进，Radicchi提出了使用边聚类系数的S

7、elf-ContainedGN算法[12]；Fortunato等人提出了信息中心性的概念，即经过从图中移除某节点及与此节点相连接的边后，引起图效率的相对衰退[13]；Nean[14]于2004年提出了以模块度作为衡量算法优化条件的算法，其本质是一种贪心算法，直到达到模块度最大时，所划分的社区即为最佳社区；以模块度函数作为优化条件的方法逐渐出现，Guimerà和Ameral[15]将模拟退火方法首次应用于社区发现中，通过不断的优化模块度函数寻找最优解；Duch和Arenas则提出极值优化方法[16]，通过优化模块度函数，节点进行转移达到最终稳定

8、状态；Blonde等提出的多层次贪心合并算法[17]是目前既具有最快的执行速度，同时也具有较高准确率的算法之一。......第2章社区发现与中心性分析2.1社会网络