基于路径相似度的社区检测方法

第３４卷第３期　内蒙古工业大学学报　Ｊ０ＵＲＮＡＬ　ＯＦ　ＩＮＮＥＲ　ＭＯＮＧＯＬＩＡ　ＵＮＩＶＥＲＳＩＴＹ　０Ｆ　ＴＥＣＨＮｏＬＯＧＹ　

文章编号：１００１—５１６７（２０１５）０３—０００３—０６　

基于路径相似度的社区检测方法　

刘维维，陈建芮　，乌力吉　（内蒙古工业大学理学院，呼和浩特０１００５１）　

摘要：本文提出一种基于相似度的复杂网络社区检测算法。在原有Ｋｕｒａｍｏｔｏ振荡器相位同步的　基础上，为了使两个连接振荡器的相位同步，两个不相连振荡器的相位异步，加入了基于路径的相　似度计算函数。节点的不同邻居有不同的亲密关系，有亲密关系的节点更有可能在一个社区，而　节点的相似度就是描述他们之间的亲密程度。在这种改进模型的基础上，整个网络会分为几个相　位值不同的同步簇。为了验证算法的性能，本文针对空手道网络，海豚网络进行了仿真并与已有　文献作相关比较取得一定的优势。　关键词：复杂网络；社区检测；相似度；同步；异步　中图分类号：０１７５．２９　文献标识码：Ａ　

０　引言　近年来，随着对各种各样网络的研究，例如社交网络，生物化学网络，信息网络等，发现这些网络既　不是传统的规则网络，也不是随机网络，而是具有与前两者皆不同的具有统计特征的网络，这样的一些　网络被学者们称之为复杂网络。复杂网络中的一个重要特性是社区结构。社区结构表现为社区内节点　间联系紧密，社区间联系稀疏的聚团性质。发现社区结构对于人们分析复杂网络的拓扑结构，在一定的　范围内对事物的发展和运行进行简单的预测具有非常重要的理论意义。　为了研究复杂网络中的社区结构，一些经典的算法如ＫｅｒＮｉｇｈａｎＬｉｎｌ】　算法、谱平分算法（Ｓｐｅｃｔｒａｌ　Ｂｉｓｅｃｔｉｏｎ　Ｍｅｔｈｏｄ）Ｉ２］，ＧＮ（Ｇｉｒｖａｎ－－Ｎｅｗｍａｎ）『３　算法等。近年来涌现了很多新的算法：吴建设等人＿４　采　用基于Ｋｕｒａｍｏｔｏ振荡器相位同步的网络动力学社区检测算法，该算法加入负耦合强度，使不存在连接　的节点相位在振荡过程中相互分离，以此形成不同的同步簇，同时在标准的测试集中验证了该算法的有　效性和可靠性。陆蕊等人　给出了基于网络相位聚类模型进行社区检测算法，在该模型中，存在一对相　互作用的力，即相互吸引力和相互排斥力，由于这两对力的存在，网络中每个节点的相位跟它的所有邻　居节点的平均相位愈来愈接近，而跟它的所有非邻居节点的平均相位愈来愈远离，这样，当所有节点的　相位稳定不变时，节点的相位将根据连接关系自动聚类。陈建芮等人Ｌ６　基于模块矩阵动态演化社区检　测算法。该算法主要采用同步动态演化来进行社区检测，并给出ＤＥ　Ｍ，ＤＣ　Ｍ。两种算法。　

１　复杂网络社区结构划分算法　算法的基础模型是采用原Ｋｕｒａｍｏｔｏ＿７　振荡器改进模型，在此基础上加入了基于路径的相似度函　数，函数中的参数可以根据网络的聚合程度进行调整。在复杂网络中，节点的不同邻居有不同的亲密关　

收稿日期：２０１５—０６—１５　作者简介：刘维维（１９９１一），女（汉族），内蒙古集宁人，在读硕士研究生，研究方向：运筹学与控制论。　＊通讯作者：陈建芮（１９７９一），女，副教授，研究方向：应用数学。　基金项目：国家自然科学基金天元基金（Ｎｏ．７１５６１０２０，６１５０３２０３，１１３２６２３９）；内蒙古自治区自然科学基金（Ｎｏ．　２０１５ＭＳ０１０３）；内蒙古自治区高等学校科学研究项目（Ｎｏ．ＮＪＺＹ１３１１９）。　１７２　内蒙古工业大学学报　系，有亲密关系的节点更有可能在一个社区。例如在社会网络中，好朋友比普通朋友在一个社区的概率　要大，而节点的相似度使这种亲密程度很好的体现出来。　１．１　复杂网络动态演化模型　文献改进的Ｋｕｒａｍｏｔｏ振荡器Ｅ６３相位同步模型如下：　

一　＋　∑　一　）＋　∑（１一ａ　）ｓｉｎ（　一　）　（１）　’Ｊ－＿１　’Ｊ　ｌ　其中，Ｋ。＞Ｏ，Ｋ　≤０，ｅｉ和６０ｉ表示第ｉ个振荡器（节点ｉ）的相位和固有频率，Ｎ是网络的节点数，也可　

以被网络最大的节点度或者第ｉ个振荡器的度代替，正耦合系数Ｋ。使两个连接的振荡器之间的相位相　互聚集，而更重要的是，负耦合系数使两个不相连的振荡器之间的相位相互发散。当ｊ是ｉ的邻居时　ａ　＝＝＝ｌ，否则ａ。　一０。这样社区能够很好的检测出来。现将上式重写为：　

一　＋　∑　（　一　）＋　∑　（　一　）　（２）　‘’ＪＣ－Ｎｉ　’ＪＥＮｉ　其中Ｎ．表示ｉ节点所有邻居的集合。加入的相似度能更好地体现节点间的亲密程度，由此实现高　

效的社区检测。本文所采用的相似度源于文献Ｄｏ］，在无向网络Ｇ（Ｖ，Ｅ）中，节点ｖｉ，ｖｉ的相似度定义如　下：　（ｉ，Ｊ）一　Ｘ　Ｎｌ＋　２　Ｘ　Ｎ２＋Ａ。Ｘ　Ｎ３＋…＋　Ｘ　Ｎ　（３）　Ｎ　，Ｎ：，Ｎ。，Ｎ　表示节点ｖ。，ｖ　之间长度分别为１，２，３，…，ｍ的路径长度的数目，入　，　，　，…，入　为　系数，　取值为网络平均度的路径长度次幂的倒数，即　

＝＝＝去　㈩　

而从实验结果来看，参数的选择对网络社区划分结果也有很大的影响，这里选取的最长路径长度为　３，这样既保证了能够在相似度中体现足够多的局部信息，又没有很大的计算量。即　Ｓ　一　１×Ｎ１＋　２　Ｘ　Ｎ２＋　３×Ｎ３　（５）　加入相似度Ｓ（ｉ，ｊ）后，本文所提出的相似度模型为：　

一　善Ｓｏｓｉｎ（　一　）＋　善Ｓｏｓｉｎ（０，一　）　（６）　公式（２）中，因为∞　对本文提出的算法影响不大，所以在公式（６）中把ｍｉ删去，网络中的节点相位按　照网络模型（６）动态演化，整个网络会分为几个平均相位不同的同步簇。　１．２算法的详细流程　这一部分，将详细给出基于路径的相似度社区检测方法算法流程和具体步骤。　具体步骤如下：　第一步：根据已有的测试网络，输入相对应的网络邻接矩阵。　第二步：根据公式（５）计算节点问的相似度。　第三步：节点相位初始化。初始相位ｅｉ一般在Ｅｏ，２丌］内随机产生，给定正负耦合系数值，其中，Ｋ　＞　０，Ｋ　≤０。　第四步：在模型（６）中，网络中的每一个节点都对应一个相位值，通过（６）的动态演化，若可以使同一　个社区内的节点聚集，而不同社区间的节点相位相互分离，从而形成不同的同步族，则跳出程序，否则返　回第二步调整参数Ｋ的值，直到所有节点被正确的划分在不同的社区。　１．３　实验仿真与结果分析　在复杂网络中，一个社区中的节点连接是积极的，不同社区的节点连接是消极的。这里，本文使用　

一个有１Ｏ个节点的计算机生成网络来进行仿真。参数Ｎ一１０，Ｋ　一６，Ｋ　一一３。　在图２（ａ）中，正方块代表一个社区，圆形块代表在一个社区，可以发现这样一个现象，不仅一个社区　间有连接，不同的社区间也有连接。这样，社区间的连接为社区的检测增加了难度。　第３期　刘维维等基于路径相似度的社区检测方法　１７３　图１　复杂网络算法流程图　Ｆｉｇ．１　Ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋ　ａｌｇｏｒｉｔｈｍ　ｆｌｏｗ　ｃｈａｒｔ　具体步骤如下：　第一步：计算机生成网络邻接矩阵为：　

Ｗ＝＝　第二步：根据公式（５）计算节点间的相似度（因为篇幅较大，这里只保留小数点后两位数字）。　Ｗ＝＝　－１．０１，１０３８，１．２５，１．４５，１．４８，１．４１，０．２６，０．７８，０．１７，０．１７　１．３７，３．３１，２．０８，２．６７，３．３１，２．４３，０．７８，１．５９，０．４０，０．４０　１．２５，２．０８，１．８４，１．９１，２．２２，２．０５，０．３７，１．Ｏ１，０．２３，０．２３　１．４５，２．６７，１．９１，２．６７，２．８６，２．２４，０．７４，１．４９，０．３９，０．３９　１．４８，３．３１，２．２２，２．８６，３．９８，２．９２，０．９９，１．６６，０．８１，０．８１　１．４１，２．４３，２．０５，２．２４．２．９２，３．０３，０．８７，１．６２，１．１７，１．１７　０．２６，０．７８，０．３７，０．７４，０．９９，０．８７，１．３４，１．５Ｏ，０．９６，０．９６　０．７８，１．５９，１．０１，１．４９，１．６６，１．６２，１．５０，２．０４，１．０９，１．０９　０．１７，０．４０，０．２３，０．３９，０．８１，１．１７，０．９６，１．０９，１．４３，１．２１　０．１７，０．４０，０．２３，０．３９，０．８１，１．１７，０．９６，１．０９，１．２１，１．４３　

０　０　０　Ｏ　０　Ｏ　ｌ　１　１　０　Ｏ　０　Ｏ　０　Ｏ　１　１　Ｏ　Ｏ　Ｏ　０　Ｏ　１　１　０　Ｏ　１　０　０　０　０　０　１　Ｏ　Ｏ　１　Ｏ　ｌ　０　１　１　Ｏ　１　１　Ｏ　１　１　１　１　Ｏ　１　Ｏ　１　０　０　１　１　Ｏ　１　１　Ｏ　Ｏ　０　Ｏ　１　Ｏ　１　１　０　０　０　０　１　０　１　１　１　１　０　Ｏ　０　ｌ。１　Ｏ　０　１　Ｏ　０　Ｏ　Ｏ　ｌ７４　内蒙古工业大学学报　第三步：求解各个节点的相位值。这１０个节点的初始相位值为　ｘ（０）一（４．７２０４，１．６０２８，３．１７９，４．３９２４，５．５９７７，６．０２７４，３．４３８３，０．８７１，０．９３８０４，１．６１８）　第四步：通过（６）的动态演化，发现节点１，２，３，４，５，６在一个社区，７，８，９，１０在一个社区，如图２（ｂ）　所示。　

（ａ）　（ｂ）　图２红色方块是一个社区，蓝色圆圈是一个社区。（ａ）社区网络结构图；（ｂ）节点相位演化图　Ｆｉｇ．２　Ｓｑｕａｒｅ　ｎｏｄｅｓ　ａｒｅ　ｉｎ　ｔｈｅ　ｓａｍｅ　ｃｏｍｍｕｎｉｔｙ．Ｃｉｒｃｌｅ　ｎｏｄｅｓ　ａｒｅ　ｉｎ　ｔｈｅ　ｏｔｈｅｒ　ｃｏｍｍｕｎｉｔｙ．　（ａ）Ｔｏｐｏｌｏｇｙ　ｓｔｒｕｃｔｕｒｅ　ｏｆ　ｔｈｅ　ｎｅｔｗｏｒｋ（ｂ）Ｓｔａｔｅ　ｏｆ　ｔｈｅ　ｎｏｄｅｓ　ｅｖｏｌｖｉｎｇ　ｗｉｔｈ　ｔｉｍｅ　１．４对标准测试集的仿真并与靳超进行对比　１．４．１　测试空手道俱乐部网络（ＺａｃｈａｒＦｓ　ｋａｒａｔｅ　ｃｌｕｂ　ｎｅｔｗｏｒｋ）　这个网络是ＷａｙｎｅＺａｃｈａｒｙ在１９７７年提出的ｎ　，它作为ｂｅｎｃｈｍａｒｋ被广泛地应用到进行社区检测　的实际网络。该网络由３４个节点组成，代表了Ｋａｒａｔｅ俱乐部的成员，７８条边代表了成员之间的友谊关　系，由于俱乐部中主管和校长之间产生了矛盾，导致该俱乐部分裂成了分别以主管和校长为中心的两个　小的俱乐部。图３（ａ）（ｃ）是本文所提出算法的实验结果，（ｂ）（ｄ）是文献［４］算法。其中Ｋ。一４０，Ｋ　一一　３０。　由图３易见，本文所提出的算法在划分社区结果上更为直观，而且不需要后处理。文献［４３在划分　结果不明显时还需要进行后处理，进一步计算模糊节点的归属社区。　由图４可见，我们的算法社区划分结果更好，两个社区独立划分，不存在模糊不清的社区。　１．４．２测试海豚社会网络　这个网络是对生活在新西兰神奇湾的６２只海豚经过７年的研究构造的［１引，网络的节点代表６２只　海豚，经过从１９９４年到２００１年问的长期观察，建立了这些海豚之间的社会关系，这些社会关系组成了　节点之间的连接边，如果一对海豚之间的联系比偶然预计的联系更频繁，则它们之间建立连接边。该海　豚关系网络自动分裂成了两个较小的族群，即该网络结构由两个社区组成。图４（ａ）是本文所提出算法　的实验结果，图４（ｂ）是文献Ｉ－４］算法。其中Ｋ。一５，Ｋ　一一３。