, 任涛东北大学 软件学院, 辽宁 沈阳 110169
收稿日期：2017-06-26
基金项目：辽宁省自然科学基金资助项目(20170540320)；辽宁省教育厅科学研究项目(L20150167)；辽宁省博士科研启动基金资助项目(201601007)。
作者简介：黄新宇(1990-), 男, 辽宁凌源人, 东北大学博士研究生;
陈东明(1968-), 男, 安徽怀宁人, 东北大学教授;
任涛(1980-), 男, 辽宁沈阳人, 东北大学教授。
摘要：分析了真实社会网络的特性, 建立了节点间多关系网络模型.在此基础上定义了节点间相互作用的影响力等概念, 提出了适用于多关系网络的社团发现算法.通过理论验证了相关定义的合理性, 并针对多关系网络进行了对比实验.实验结果表明:所提出的多关系网络社团发现算法与其他经典算法相比具有较高的精确度和较低的时间复杂度, 具有重要的研究意义及实用价值.
关键词：在线社会网络多关系网络社团发现异质网络重叠社团
Community Discovery Algorithm for Multi-relationship Networks
HUANG Xin-yu, CHEN Dong-ming
, REN TaoSchool of Software, Northeastern University, Shenyang 110169, China
Corresponding author: CHEN Dong-ming, E-mail: chendm@mail.neu.edu.cn
Abstract: The characteristics of the real social network were analyzed, and a network model with multi-relationships network between nodes was established. Based on this, the concept of influence of interaction between nodes was defined, and a community discovery algorithm for multi-relationship network (CDMN) was proposed. The rationality of the presented definitions was verified theoretically, and a series of experiments compared with other algorithms were conducted. Experimental results showed that the proposed community discovery algorithm for multi-relationship networks has higher accuracy and lower time complexity than other classical algorithms, and has important research significance and practical value.
Key words: online social networkmulti-relationship networkcommunity discoveryheterogeneous networkoverlapping community
随着信息技术的飞速发展, 社会网络已经成为人们日常生活中的一部分, 国内外学者对此研究也越来越深入.传统的复杂网络研究大都对网络简化处理, 形成简单的图模型进行信息挖掘.然而, 社会网络在真实环境中更为复杂, 个体间具有多种关系, 对应网络的多个维度，也就构成了异质网络[1].异质网络就是网络中节点和关系具有多重属性, 对外表现出不同类型的节点和关系, 构成了非同质不均匀的复杂网络结构.而本文研究的多关系网络是异质网络问题中的一种特例, 即存在于多个网络中的节点是互相对应的同类节点, 节点间的关系是多种多样的.
国内外学者主要从网络重叠结构、动态变化等方面对此类问题展开研究, 研究方法多采用指数分布随机图模型、关系代数和分块模型等方法[2-3].Xie等[4]针对网络重叠程度提出了不同方法, 并对真实社会网络重叠情况进行概括, 指出约30%的节点是属于2~3个社团的重叠节点, 在重叠社团发现问题上具有重要的参考价值, 但是在算法普适性方面有待优化.Cazabet等[5]将动态网络划分成多个时间切片, 然后将每个时间切片对应的静态网络进行社团划分, 再将结果进行合并, 能够给出较为准确的动态网络划分结果, 但也揭示出算法依赖于处理时间先后顺序, 对于大规模网络的动态划分问题存在改进空间.李慧嘉等[6]利用动态迭代技术提出了一种动态网络社团划分指标函数的一般化形式, 使动态网络社团划分不需要任何参数就可以得到最优化的结果, 但在多关系网络处理方面存在不足.
节点重要性测度是网络研究中的一项基本指标, 国内外学者对此有很多研究基础[7-9].就现有方法来说, 最简单的办法就是考虑节点的度, 即节点的度越大该节点越重要.这种方法的缺点是容易漏掉那些在多个社团之间起桥梁作用的节点, 虽然这些节点的度不大, 但它们对于多个社团聚合成大型社团至关重要.因此, 介数的定义被提出, 但因为其计算复杂性, 对结构无法预知的网络往往只能采取近似计算.除了聚类系数、k-核等经典指标, 也有学者提出基于PageRank改进的NodeRank指标, 用于评价大规模加权网络的节点重要性测度, 并验证了其可靠性[10].大多数现有评价指标不是单纯从网络拓扑角度出发考虑节点重要性, 就是从某个现实领域出发给出对节点重要性的理解.事实上节点的重要性同时受多种因素影响, 从多个角度考虑节点重要性的方法能获得更好的效果.
综上所述, 到目前为止异质网络的研究方兴未艾, 随着大数据时代的到来, 复杂多元化网络分析具有非常重要的研究意义.
1 模型与方法在社会网络中, 每个人在不同时期担负着不同的角色, 并且大部分肩负多种角色, 各个角色都可以看作一种社会关系, 多种社会关系构成的多个网络通过个人的参与映射成了一个多关系网络.在多关系网络中, 人们受到社会环境的影响, 却能够在社会环境中保持稳定状态, 正如经典物理学中力的合成, 如图 1所示.
图 1(Fig. 1)
 | 图 1 物理学中力的合成Fig.1 Synthesis of forces in physics |
在多关系网络中, 假设节点A和节点B代表 2个人, 既是同学关系也是同事关系, 那么在同质网络中可能仅仅能够表示出A和B之间存在连边, 但在多关系网络中就能够呈现出更细致的关系.本文建立的网络模型具有多种关系类型和对应的权值, 表述如下:
 | (1) |
为了描述节点间多种关系的相互作用, 本文定义节点影响力F的计算式为
 | (2) |
 | (3) |
 | (4) |
 | (5) |
此外, 重叠节点连接多个社团, 在社团划分问题中尤为重要.对于网络中连接多个社团的重叠节点o, 与社团C之间的判定规则R如下:
 | (6) |
2 算法描述假设给出参数k用于表示需要得到的社团数目, 本文设计的CDMN算法执行步骤如下.
步骤1??数据预处理, 进行网络初始化并计算各节点的影响力Fi, 得到节点影响力的有序列表;
步骤2??获取网络中节点影响力较大的k个节点, 初始化k个社团, 并将这些节点的非重叠邻居节点划入社团Ci;
步骤3??将网络内其他非重叠节点划分到与已有社团直接相连的社团内;
步骤4??针对网络中剩余的重叠节点, 采用式(6)中的判定规则R进行判定, 划分到相应的社团.
CDMN算法执行的伪代码如下所示.
| Algorithm: CDMN |
| ??INPUT:网络数据集 |
| ??OUTPUT:社团划分之后的节点集合 |
| ??//初始化节点, 计算影响力 |
| ??For n in Nodes do |
| ????Calculate Fi |
| ??End For |
| ??//按节点影响力大小排序, 初始化社团 |
| ??sortedNodes = Sort Nodes by Fi |
| ??initCommunities = sortedNodes[0:k] |
| ??For i in k: |
| ????Put n into Community i |
| ??????Put n's non-overlapping neighbors into Community i |
| ??End For |
| ??//将非重叠节点划入临近社团 |
| ??For n in non-divided sortedNodes do |
| ????Calculate AC of Communities. |
| ????Divide n into adjacent Community. |
| ??End For |
| ??//将重叠节点按式(6)的R规则划分 |
| ??For o in overlapping non-divided sortedNodes: |
| ????Divide o into Community according rule R |
| ??End For |
假设网络中有N个节点, CDMN算法对给定网络中节点只需要执行一次遍历即可计算出各个节点的影响力, 在社团划分过程中需要再执行一次遍历, 得到社团个数为k, 考虑重叠节点的划分问题, 总体时间复杂度为O(N+N+kN), 由于k通常远远小于N, 因此可近似化简为O(N), 优于FastNewman算法时间复杂度.由于处理重叠节点的划分问题, CDMN算法的时间复杂度高于LPA算法.在空间复杂度方面, CDMN算法存储网络使用树结构, 空间复杂度为O(N), 最终转化为邻接矩阵形式, 与FastNewman算法、LPA算法的矩阵存储无明显差异.
3 实验分析实验操作系统环境为Windols 10×64教育版, 内存为8G DDR4, CPU为Inter(R) Core(TM) i7-4790 @ 3.6GHz, 编程语言为Python 2.7.13.
为了验证算法的有效性, 本文首先采用经典网络数据集空手道俱乐部网络[11]进行实验, 通过CDMN算法读取网络中的节点, 计算其影响力, 结果如表 1所示.
表 1(Table 1)
 表 1 节点影响力计算结果Table 1 Calculation results of nodes' influence
| 表 1 节点影响力计算结果 Table 1 Calculation results of nodes' influence |
设定参数k=2, 执行CDMN算法得到2个以0号节点(Mr. Hi)和33号节点(Officer)为核心的2个社团, 模块度为0.2106, 略高于实际情况的模块度[12](0.2040), 划分结果如图 2所示.
图 2(Fig. 2)
 | 图 2 空手道俱乐部网络实验结果Fig.2 Experiment results of karate club network |
由图 2可以看出:网络划分结果与俱乐部后来的发展趋势一致, 验证了算法的有效性.选取“9·11”恐怖袭击网络数据集[13]验证CDMN算法，结果如图 3所示.
图 3(Fig. 3)
 | 图 3 “9·11”袭击网络实验结果Fig.3 Experiment results of "9·11" attack network |
通过计算, 网络数据集中用户的影响力计算结果如表 2所示.
表 2(Table 2)
表 2 “9·11”袭击网络节点影响力计算结果Table 2 Calculation results of nodes' influence in "9·11" attack network
| 表 2 “9·11”袭击网络节点影响力计算结果 Table 2 Calculation results of nodes' influence in "9·11" attack network |
通过表 2给出网络中影响力较大的用户在各自所在的社团内处于核心位置, 更容易策动反动活动, 在实际应用中具有重要意义.
在目前公开的网络数据集中, 很少有涉及网络中节点存在多关系的情况.作者构建了1个在线社交网络平台, 实现了注册登录、组织活动、交流分享的平台, 并邀请了200多名学生注册使用.该平台中多种不同社交活动表示网络中的多种关系, 运行CDMN算法结果如图 4所示.
图 4(Fig. 4)
 | 图 4 本文构建的社交网络实验结果Fig.4 Experiment results of the established social network proposed in this paper |
通过与真实网络对比, 发现网络中影响力较大的节点大都是平台中负责推广的老师和学生, 因为其邀请很多其他用户, 在网络中具有较高的影响力, 因此更容易形成社团的核心.
此外, 本文选取LPA算法、FastNewman算法与CDMN算法进行对比, 设定相同参数及数据集, 为了兼顾算法运行时间与划分效果, LPA算法迭代次数参数设定为1000, CDMN算法与其他算法运行时间对比如图 5所示.
图 5(Fig. 5)
 | 图 5 算法运行时间对比Fig.5 Comparison of algorithms' running time |
从图 5可知, CDMN算法与LPA算法运行时间基本在同一数量级, 由于对重叠节点的判定，故运行时间略多于LPA算法, 但是远少于FastNewman算法的运行时间.CDMN算法与其他算法的模块度对比如图 6所示.
图 6(Fig. 6)
 | 图 6 算法模块度对比实验Fig.6 Comparison of algorithms' modularity |
从图 6可知, 本文所提出的CDMN算法划分效果优于FastNewman算法和LPA算法.综上所述, 本文所提出的算法具有较好的划分效果和较低的时间复杂度.
4 结语本文建立了节点间多关系的网络模型, 在此基础上, 定义了节点的影响力等概念, 并通过数学归纳法给出社团稳定状态的评判标准, 对于网络中的重叠节点着重考虑, 给出了较好的划分结果.为了深入研究多关系网络, 本文设计了社交网络实验平台, 并设计多种交互方式用于收集多关系网络数据进行实验.对比实验结果表明本文所提出的算法在较低的时间复杂度下获得了较好的划分效果.
参考文献
| [1] | Du S, Niu K, He Z, et al.Community detection analysis of heterogeneous network[C]// International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery.Xi'an, 2015: 509-512. |
| [2] | Zhang H, Wang C D, Lai J H, et al. Modularity in complex multilayer networks with multiple aspects:a static perspective[J].Applied Informatics, 2017, 4(1): 1–7.DOI:10.1186/s40535-016-0029-7 |
| [3] | Bródka P, Kazienko P. Multilayer social networks[M]. New York: Springer, 2017. |
| [4] | Xie J, Kelley S, Szymanski B K. Overlapping community detection in networks:the state-of-the-art and comparative study[J].ACM Computing Surveys, 2011, 45(4): 1–35. |
| [5] | Cazabet R, Amblard F. Dynamic community detection[M]. New York: Springer, 2014. |
| [6] | 李慧嘉, 李爱华, 李慧颖. 社团结构迭代快速探测算法[J].计算机学报, 2017, 40(4): 970–984. ( Li Hui-jia, Li Ai-hua, Li Hui-ying. Fast community detection algorithm via dynamical iteration[J].Chinese Journal of Computers, 2017, 40(4): 970–984.) |
| [7] | Ai X. Node importance ranking of complex networks with entropy variation[J].Entropy, 2017, 19(7): 303–310.DOI:10.3390/e19070303 |
| [8] | Lü L, Chen D, Ren X L, et al. Vital nodes identification in complex networks[J].Physics Reports, 2016, 650: 1–63.DOI:10.1016/j.physrep.2016.06.007 |
| [9] | 韩忠明, 陈炎, 刘雯, 等. 社会网络节点影响力分析研究[J].软件学报, 2017, 28(1): 84–104. ( Han Zhong-ming, Chen Yan, Liu Wen, et al. Research on node influence analysis in social networks[J].Journal of Software, 2017, 28(1): 84–104.) |
| [10] | Pan Y, Tan W, Chen Y.The analysis of key nodes in complex social networks[C]// Cloud Computing and Security of the Third International Conference.Nanjing, 2017: 829-836. |
| [11] | Zachary W W. An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research, 1977, 33(4): 452–473.DOI:10.1086/jar.33.4.3629752 |
| [12] | Newman M E, Girvan M. Finding and evaluating community structure in networks[J].Physical Review E, 2004, 69(6): 026113. |
| [13] | SNABook.9_11_edgelist.txt[EB/OL]. (2011-08-17)[2017-06-27]. https://github.com/maksim2042/SNABook/blob/master/chapter4/9_11_edgelist.txt. |
