复杂网络中社团发现算法的研究

黄蓝会(宝鸡文理学院计算机学院， 宝鸡 721016)

复杂网络中社团发现算法的研究

黄蓝会
(宝鸡文理学院计算机学院， 宝鸡 721016)

基于复杂网络模型，将数据挖掘中的聚类分析方法应用到社团发现中，提出了结合模块度的基于层次聚类的社团发现算法。由层次树得到的社团结构层次清晰，仿真实验证明，利用该算法，当信号传播次数取值为3时社团划分准确度最高。

复杂网络； 网络聚类； 数据挖掘； 社团发现

0 引言

复杂网络是一个涉及数学、统计物理学、计算机科学、生态学、生物学、经济学、社会学、自动控制等众多领域的交叉学科。[1]复杂网络利用数学上图论的概念，将网络中的个体抽象为图中的节点，个体之间的相互作用抽象为图中节点之间的连边。因此，任何包含大量个体单元的复杂系统都可以当作复杂网络来研究，如豆瓣网、当当网等。复杂网络结构具有小世界、无标度、高聚集和社团结构等特性，其中社团结构的特点是同一个社团内部节点之间连接紧密，不同社团之间连接松散。针对复杂网络进行社团划分是数据挖掘领域最活跃的研究方向之一，比如豆瓣网中大部分用户是根据自己的兴趣爱好选择好友，社团划分可以让用户注册成功后快捷地找到其想加入的群体；当当网进行社团划分后，可以针对同一社团群体用户建立推荐系统，引导用户消费。

聚类分析是将物理或抽象对象的集合分成由类似的对象组成的多个类(Class)或簇(Cluster)的分析过程，聚类分析的结果是同一个簇中的对象有极大的相似性，而不同簇之间的对象则差别较大[2]。从定义上发现复杂网络的社团结构的概念和聚类分析中的类的概念很相似，复杂网络中的社团相当于聚类分析中的类，复杂网络节点的连接相当于类的相似性，寻找复杂网络社团结构相当于与在聚类数据中发现数据潜在的规律。本文考虑将聚类分析方法应用到复杂网络的社团发现中。

1 相关研究

Hu等人提出了在复杂网络中利用信号传播将网络中的节点转化成代数空间上的数据对象的方法[3]。Pan等人[4]提出了基于相似度的复杂网络社团划分算法，该算法采用节点之间的共同邻居数来对节点之间的相似度进行评估，进而对网络进行社团划分。Lou等人[5]通过共同邻居对节点相似度进行计算，然后在此基础上使用标签传播算法进行社团划分。Yuan等人[6]提出了一种基于簇相似度的复杂网络社团划分算法，该算法主要用于检测边密度较高的复杂网络中的社团结构。王兴元等人[7]在共同邻居的基础上提出了节点依赖度，并依据节点依赖度对社团进行划分。

2 社团发现算法

本文根据豆瓣网设计了一个基于复杂网络的在线社会网络演化模型[8]，该模型将网络中的每个节点看作一个信号节点，具有n维向量，n个节点就有n个n维向量，将这n个向量标准化后投射到代数空间后，认为每个向量即为代数空间中的一个数据。定义了相似性系数公式，通过比较两个节点的相似性系数来判断是否属于同一社团。

复杂网络中层次凝聚聚类方法被广泛用来进行社团的划分，其基本思想是先将网络中的每一个节点视为一个社团，同时设定一个判断两社团相似的衡量标准，然后计算社团之间的相似度，相似度高的社团合并后产生一个新的社团，继而重新计算相似度，直至所有节点都凝聚成一个社团或者到达网络中最大的Q值后终止凝聚，通过这个思想最终得到的是一棵层次聚类树。

基于上述定义，本文设计了一个考虑局部模块度，基于层次聚类的社团发现算法，算法步骤如下：

(1) 假定复杂网络定义为G=(V,E,R,F)；

(4) 计算所有节点的综合特征值CFi，并按照特征值的升序排列；

(5) 选择CFi最小的节点作为起始节点，设置该节点的局部模块度值为0；

(6) 合并节点，选择节点的相似性系数disij最大的两个合并，根据合并后的Q值判断是否停止聚类，当Q值最大时得到最终的社团分类。

3 实验结果与分析

本文以豆瓣网为实证网络，使用自己编写的网络数据抓取及解析程序[10]，采用多次仿真取平均值的方法来获得演化模型的网络拓扑值。本次实验主要测试传播次数T的选择和社团划分准确性的关系，算法中仿真网络选择100个节点，T值从1-10，Cout表示每个节点和其他社团节点之间有连边的最大值，当Cout变化时，T取不同的值社团划分的准确率，如图1所示。

图1 T值的选择与社团划分准确率的关系

从图1中可以看到，Cout=6和Cout=4比较，Cout取值越大，社团发现准确率变差，同时发现T的取值和Cout的关系有一个共同的规律，当T=3时，都是该条折线图准确率的最高点，因此可以得出一个结论，当T=3时，社团划分准确率最高。

4 总结

社团发现是复杂网络的重要研究内容之一，互联网上存在着大量Web 服务，这些服务通过用户的需求的交互连接，形成了一个复杂的交互网络，发现并利用这些交互网络上的社团结构有助于理解这类复杂软件系统的行为，促进在网络中开展信息分享、商品推荐、广告投放等个性化商业应用。

[1] 郭世泽, 陆哲明. 复杂网络基础理论[M].北京:科学出版社, 2012.

[2] Jain A K, Murty M N, Flynn P J. Data clustering: a review[J]. ACM Computing Surveys(CSUR),1999,3l(3):264-323.

[3] Yan-qing Hu，Meng-hui Li，Peng Zhang. Community detection by signaling on complex networks[J]. Phys. Rev. E,2008,78:016115.

[4] Pan Y, Li D H, Liu J G, et al. Detecting community structure in complex networks via node similarity [J]. Physical A Statistical Mechanics & Its Applications, 2010, 389(14):2849-2857.

[5] Lou Hao, Li Sheng hong, Zhao Yu xin. Detecting community structure using label propagation with weighted coherent neighborhood propinquity[J]. Physical A: Statistical Mechanics and its Applications, 2013, 392(14): 3095-3105.

[6] Yuan C, Chai Y. Group similarity based algorithm for network community structure detection[J]. Acta Physica Sinica, 2012, 61(21):514-518.

[7] 王兴元, 赵仲祥.基于节点间依赖度的社团结构划分方法[J].物理学报, 2014, 63(17):178901.

[8] 黄蓝会. 基于社会媒体网络的聚类方法的研究[J].微型电脑应用,2016,32(6):1-2.

[9] 宾晟. 基于多子网复合复杂网络模型的多关系在线社会网络研究[D].济南：山东科技大学,2014.

[10] 黄蓝会. 基于在线社会网络的网络爬虫的研究和设计[J].电子设计工程,2014,22(6):106-108.

ReseachontheCommunityDiscoveryinComplexNetwork

Huang Lanhui
(School of Computer, Baoji University of Arts and Science, Baoji 721016)

Based on complex network，clustering analysis method in data mining is applied to the research of community detection. A new measured method for node similarity--node dissimilarity coefficient in multi-subnet composited complex network is proposed. A community detection algorithm in complex network based on hierarchical clustering is proposed. By using this algorithm, community classification derive from the hierarchical tree is very clear. Experiments prove that when the number of signal propagation is 3, high accuracy rate of community classification are

in network.

Complex network; Network clustering; Data Mining; Community discovery

TP311

A

2016.07.25)

国家自然科学基金(61379030)，陕西省教育厅专项科研项目(15JK1028)

黄蓝会(1980-)，女，湖南岳阳人，硕士，讲师，研究方向：物联网应用，数据挖掘.

1007-757X(2017)10-0011-02