基于共同邻居相似度的社区发现算法-论文.pdf

《基于共同邻居相似度的社区发现算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ACADEMICRESEARCH学术研究基于共同邻居相似度羽祜区发坝算法◆仇丽青陈卓艳摘要：社区发现是社会网络的一个重要研究方向。社区发现通过分析网络拓扑结构和其他性质发现一些小的团体．使得团体之间的连接较为稀疏而团体内部的联结比较稠密。本文首先提出了共有邻居相似度的定义，把共有邻居相似度作为衡量两个节点相似度的唯一标准，如果两个节点的共有邻居相似度高于预先设定的阈值，则认为这两个节点相似，属于同一个社区。然后设计提出了基于共同邻居相似度的社区发现算法，并给出了详细的设计步骤和说明。关键词：社会网络；社区发现；共同邻居相似度的复杂性。目前的

2、社区发现算法主要有这么几类：引言(1)图分割算法pl。利用数学领域的成熟的图理论，社会网络的研究始于20世纪二三十年代，最初是由社通过预先定义一个聚类数目，然后将网络进行分割。(2)会学家研究的。其中，社会网络中的节点是指单个个体，层次聚类算法]。包括凝聚聚类和分裂聚类两种聚类手段。网络中的边是指个体间的关系，这里的关系可以是朋友、类似于传统的层次聚类，通过计算相似度将社会网络中的共同爱好或者是接触、信息交流等。到了20世纪90年代，节点划分成一个树状的层次结构。(3)模块函数算法】。社会网络的研究开始辐射到其他的学科(心理学、经济学通过定

3、义一个模块函数，使得每次聚类产生比上一次聚类等)，目前的社会网络研究呈现出多学科交融，蓬勃发展更优的模块函数值，其本质是一种贪婪算法。的局面。由于计算机可以对社会网络中的大数据进行有效这些算法各有优缺点，在实际应用时需要根据情况灵地处理，所以许多计算机专家也开始对社会网络进行分析活选择。图分割算法需要实现指定一个聚类数目，这在实研究。在这些研究中，社区发现得到了越来越多研究者的际应用中是不现实的。层次聚类算法依赖于事先定义的合关注。并或者分裂阈值，而且会产生一个树状层次结构，这与事所谓的社区发现是指通过分析网络拓扑结构和其他实是不符的。模块

4、函数算法需要遍历所有的可能性，因此性质，发现一些小的团体，使得这些团体的内部连接较为计算量非常大，当网络规模增大时，其时间复杂度和空间紧密，而团体之间的连接较为稀疏。从本质上来讲，社区复杂度变得很大。发现属于数据挖掘中的聚类。但是由于社会网络的特殊性二、共同邻居相似度(社会网络属于大规模的动态数据)，使得社区发现所采用的聚类不同于传统的聚类手段。在这种情况下，有必要对于一个复杂的社会网络而言，网络内节点自身的属设计并提m适合大规模社会网络的新型的社区发现算法。性、节点问的相互作用以及节点自身的属性、节点间的相本文以社会网络为研究对象，利用社

5、会网络中的共同互作用以及节点组成的社会网络都有可能是随着时间的变邻居属性进行相应的优化，尝试找出最优的聚类结果。值化而动态变化的，产生的网络结构复杂性与连接多样性、得注意的是，社会网络中的节点具有很多的属性，包括中网络的演化、节点复杂性与多样性以及综合的复杂性体现心度、图距离等，而本文所采用的是共同邻居属性，主要出社会网络分析问题的丰富内涵。很多研究工作表明，社是由于其计算简单，在运算效率和效果中取一个折中。会网络分析正朝着越来越复杂的方向发展。在这种背景下，我们需要设计一种能够快速实现社区发现的算法，因一、相关研究此我们提出了一种基于共同

6、邻居相似度的社区发现算法。目前的社区发现已经成为社会网络分析中一个最为重需要注意的是，该算法是一种运行效果和效率的折中，也要的应用，许多的研究者已经进行了很多具有开创性意义就是说通过牺牲部分运算效果来提高运算效率，以适应大的工作。早期的社区发现主要集中于网络的统计分析，个规模的社会网络数据。体之间的友谊模式，公司之间的商业关系模式，以及家族定义1：社会网络可以定义为一组节点，以及节点之间之间的联姻模式，都是已经被研究的网络_I]。而后随着社会关联的集合体。社会网络可以形式化描述为：网络分析技术的发展，社区的概念被提出】。社区是社会网Simi

7、larity(，v)：—neighbor(u)~neighbor(v)—r】1络的一个重要特征，它体现了社会网络的区域性特征；而neighbor(u)uneigrhbor(v)、且如果从社区的角度来研究社会网络，将有助于降低研究其中，G表示社会网络，V表示社会网络中节点的集140信息系统T程12014520ACADEMICRESEARCH学术研究>合，E表示社会网络中边的集合。四、结论定义2：共有邻居相似度认为如果两个节点“，v具有的共同邻居越多，则该两个节点的相似度越高。共有邻居相社区发现是社会网络中的一个重要研究方向。本文首似度可以形式

8、化描述为：先提出了共有邻居相似度的概念，认为如果两个节点具有Similarity(，y)：—neighbor(u)~neighbor(v)f的共同邻居越多，该两个节点的相似度越高