基于Kullback Leibler距离的二分网络社区发现方法

由于二分网络特殊的二分结构，使得基于单模网络的现有社区发现算法无法适用。提出一种基于Kullback-Leibler距离的二分网络社区发现算法，该算法将异质节点间的连接关系转换为其在用户节点集上的连接概率分布，并建立基于概率分布的KL相似度衡量节点连接模式的差异性，从而克服二分结构对节点相似性评估的不利影响，实现对二分网络异质节点的社区发现。在人工网络和真实网络上的实验和分析表明，该算法能够有效挖掘二分网络社区结构，改善二分网络社区发现的准确性和效率。1482·计算机应用研究第34卷概率分布分别为P(i)、P(j),则可以采用 Kullback-Leibler距离概率分布,得到概率分布矩阵H作为二分节点连接相似性的度量,从而刻画节点i连接模式对于二分网络来说,有节点连接概率分布得到的KL相似的趋同性或差异性。度实际反映的是二分网络社区在用户节点集U上连接选择和K(P(i)|P()=∑pnlg比的对数期望,也称相对熵( relative entropy)。当且仅当两概平二(3)倾向的相似性。K相似度起大,说明两社区的用户连接模式特征越近似;反之,则说明两社区的用户连接模式特征差异性其中:K1(P(i)‖P(j)表示两概率密度函数P(i)与P()似然越大。基于此,设计算法的具体步骤如下a)初始化二分网络G的每个节点为一个独立社区,C=率分布完全相同时,相对熵KL(P(讠)‖P(j)最小且为零。由{c1,…,c.};计算初始迕接概率分布短阵H和KL距离矩阵D于相对嫡不具有对称性,慨率分布P(i)与P(j)的相对熵距离b)遍历搜索当前矩阵D中具有最小KL相似度的社区c;、通常并不等于从P(j)到P(i)的距离,合并社区到C1。定义5KL相似度。定义一和对称的KL距离来衡量二c)删除矩阵D,H被合并社区对应的行和列,同时更新合分冈络节点基于连接概率分布的相似度,并将该度量进一步扩并后社区的连接概率分布。展为二分网络社区发现过程中两社区c;C:连接概率分布的相d)重新计算该社区与其他社区关于连接概率分布的KL似度。相似度。(c,)=KL(p(e)‖pP(c)+kL(p(c2)‖p(c1))(4)e)计算当前二分网络划分的密度模块度Qg,作为社区划其中:p(c;)表示社区c中所有节点在用户子集U上的连接概分的评价指标。率分布,d(c,c)表示社区c;与c在二分网络用户节点集U上f)重复步骤b)~e),比较二分网络社Ⅸ发现过程中不同的KL相似度。划分方案的密度模块度Q,返回具有最大Q值的社区划分作现有的相似度度量大多关注直接连接(相邻节点)范围内为二分网终最终的社区发现结果。的连接信息,在具有特殊二分结构的二分网络中局限性较大,该算法的伪代码及相关说明如下本文釆用的KL相似度考虑了全局的网络结构信息,计算复杂输入:二分网络G(U,O,E)度较低。由于二分网络节点在用户节点集上的连接概率分布输出:二分网络C具有最大密度模块度Qg的社区划分反映了节点自身的连接特征,而KL相似度通过度量节点间连1初始化每个节点为一个独立社区,C=1,…,c,}接概率分布的距离,能够直接刻画二分节点间连接模式的相似建立连接概率分布矩阵H和KL距离短阵性。由此,根据概率分布矩阵闩通过式(3)(4)得到初始规模4 for each diE D为rxr的KL相似度矩阵D。2.2算法设计6c←-{c}U{c:};合并社区c、c到c根据式(5)(6)更新矩阵H;本文算法的基本思想为:二分网络中异质节点在集合U删除矩阵D第j行J列9根据式(3)(4)更新矩阵D(或集合O)上的连接概率分布刻画了该节点的整体连接模10式,根据节点的连接概率分布计算不同节点间K离作为相//得到当前的二分网络社区划分似度庋量标准,并对一分网络进行节点聚类。将基于二分网络的密度模块度函数作为社区发现结果的评价指标,从而得到具13 end while有最优密度模块度的二分网络社团划分。14C← arg max QB(C)//返巴C作为二分网络的社区划分结果首先需要得到所有异质节点在用户节点集U上的连接概在二分网络社区聚类的每次迭代过程屮,选取具有最小率分布。对于日标节点讠:KL相似度的两社区c,、c进行合并,将c并人c,中,更新聚合(5)后的社区c1与用户节点连接的概率分布,以及其与其他社区其中:pm=(cm)/E|表示目标节点i在用户节点m上的连的K.相似度。将聚类过程中得到的所有二分N络社区划分接概率分布;a(cm)表示目标节点i与用户节点m间的连边方案记为C={C1,…,C;,…,C,},其中C;={c1,c2,…,c,}表示can的权重;|E表示二分网络G所有连边的权重之和,00.5)时,四种算法社Ⅸ发现的NM均值分别为0.70590.8306、0.8423、0.8953,上述算3.1人工网络法社区发现的准确率获得较大提升,且NM偵提升逐步变缓由于二分人工网络社区划分确定且已知,基于此的网络社社区发现性能趋于稳定。这说明在人工生成的二分网络规则区发砚结果易于比对分析,且闷络规模和社区结构的相关参数的社区结构测试环境下,直接决定二分网络社区结构强弱的社可以灵活设置,能够生成较高质量的测试网络数据。本文算法区同质系数p是影响社区发现结果的重要因素。相比Gine记为KLC,采用人工网络对算法进行验证,并与终典算法Cui-ma、BRM和ⅦBC算法,KIC算法NM值的平均增幅分别为mera等人、BRIM以及最近的MBC5算法进行比较。0.18940.0647、0.0530当P>0.5时,KLC算法NMl均值增根据文献[7]生成二分测试网络数据集,测试网络出8个幅较大且维持在较高水平,对二分网络社区发现的平均准确率社区构成,每个社区包含32个用户节点,14个口标节点。基高于89%,说明本文算法能够发现更接近于标准二分网络的于该网络配置,以0.05为步长设置ρ值,实验按照社区同质系真实社区结构。表1人工网络社区发现:三种算法结果的NMI值比较算法P=0.40p=(.45p=0.50p=0.55p=0.6p=0.65p=0.70p=0.75p=0.80p=0.85p=0.9Guimera0.22350.28470.40140.46530.56470.63300.68580.73420.76860.87950.91600.18740.22920.27590.52080.64150.77280.85400.90750.98170.98210.98460.216500.47400.57610.72130.80190.85340.92830.94520.95070.961KLC0.24700.37020.61940.68540.80330.85050.92710.94500.98230.98380.98513.2真实网络分模坎度Qg值平均增幅分別为0.0069、0.0331、0.0167;对真实二分网络相比计算机生成的测试网络更不规则,因而于 MovieLens、Cond-mt具有较强社区结构的二分网终,KLC算其社区结构往往也史加复杂。本文采用五个不同类型、不同规法的社区发现准确率改善幅度较大,相对于 Guimera、BM模的真实二分冈络数据集来进步验证算汏性能。如表2MBC算法,二分模块度Q值平均增幅分别为0.04620.092、所示, outhwomen数据集表示美国南部妇女参与活动的二分0.0188。综合KLC算法在人工网络和具实网络中的表现可以网络,连边代表某妇女参加了某项活动; Adjective-noun数据集认为:相比 Guimera、BI和MBC算法,基于异质节点在用户是基于一部小说的词语同现网络,连边表示某形容词用于修饰节点集上慨率分布的KL相似度进行社区划分的方法更适合其该名词: Movielens数据集记录了197年9月-199年4月挖掘具有二分结构的二分网络,从而得到更真实有效的社区向某网站用户对电影的评价记录,连边表示用户对该电影的评结构。价; Cond-mat数据集收录了1995-1999年间在电子预印本数表2真实网络社区发现:三种算法结果的Qg值比较据库中关于凝聚态物质的科学家及其文献记录,连边表示某科objectnetwork学家发表的相关文献; Youtube数据集表小用户兴趣群组网Guimera BRIM MBC KlC络,连边表示用户所感兴趣的群组。Southw8y0.34520.32160.34280.350由于真实一分网络的社区结构未知,可以根据本文提出的ective-noun4250.52460.49380.50830.5289二分模块度来衡量一种算法所发现社区结构的优劣,从而将基loveless16829431000000.62270.63920.63870.6553于真实网终的实验作为对人工网络实验的补充和佐证。表2Cond-ma2201516726585950.71300.73060.75180.7728给出了三种算法社区发现的二分密度模块度Q。值,准确的网YouTube94238300872933600.54280.51850.53190.5536络社区划分对应于较大的密度模块度值。由于网络结构不同,种算法的二分网络社区发现的性能也各有差异,K算法4结束语在密度模块度Q上比其他两种算法有更好的性能。本文提出了一种基于 Kullback- Leibler距离的分网络社分析表2可知,对于 Southwomen、 Adjective-noun、 Youtube区发现算法。该算法将二分网络中两类异质节点的连接选择三个具有铰弱社区结构的二分网络,KLC算法对于社区发现和倾向特征统一在用户节点集U的连接概率分布上,并基于准确率的改善幅度较小,相对于 Guimera、BRIⅥ、MBC算法,KL相似度对两类异质节点同时进行社区划分,(下转第1486页)1486·计算机应用研究第34卷性能仿真图。从图5可以看到,频率选择性衰落比瑞利平坦衰2015-10-21)[2016-03-10].hp://data.eatr.cn/bps201510落对SCⅥA系统性能影响大很多。在频率选择性信道下,系统t2U1510212131170.htm.误码率基木保持在101,北时SCMA系统基本无法正常工作。[2 Benjebbour A, Saito y, Kishiyama Y,cam. Concept and practieal随着信噪比的增大并不能缓和码间串扰引起的SCMA系统误considerations of non-orthogonal multiple access NOMA) for future码,由此说明SCMA抗频率选择性衰落能力较差。radio aceess[ C]//Proc of International Symposium on Intelligent Signal Processing and Communications Systems. 2013: 770-774[3 Wang Bichai, Wang Kun, Lu Zhaohua, et al. Comparison study of10non-orthogonal multiple access schemes for 5G[C]//Proc of IEEE Inernational Symposium on Broadband Multimedia Systems and Broad-Yu Lisu, Lei Xianfu, Fan Pingzhi, et al. An optimized design of SC101520MA codebook based on star-QAM signaling constellations[ C]//Pro信噪比of International Conference on Wireless Communications Signal Pro-图5平坦衰落信道和频率选择性衰落信道下SCMA系统误码性能cessing. 2015: 1-53结束语[5 Wei Dacheng, Han Yuxi, Zhang sihai, et al. Weighted messagepass-ing algorithm for SCMA[C]//Proe of International Conference在SCMA系统模型的基础上,本文仿真研究了瑞利平坦慢on Wireless Communications Signal Processing. 2015: 1-5衰落、瑞利平坦快衰落以及频率选择性衰落信道下SCMA系统6. Hoshyar R. Wathan F'H,1 afazolli.、 ovel low-density signature for的误码性能,并将其与LTE中上行SC-FDMA系统的误码性能synchronous CDM A syslems over AWGN channel[ J. IEEE Trans进行比较。结果表明,相比传统多址技术,sCMA能够实现在on Signal Processing, 2008, 56(4): 1616-1626有限资源下增加用户连接数的同吋获得较好的误码性能;同[7 Nikopour H, Baligh H. Sparse code multiple access[CI/ Proce of the时,sCMA也存在抗频率选择性衰落能力差的问题,因此实际IEEE International Symposium on Personal Indoor and MobileRadio Communications. 2013: 332-336应用中SCMA需结合些抗衰落技术提高系统的性能。changFrey B J, Loeliger H A. Factor graphs and the参考文献:sIIm-producl algorithm[J]. IEEE Trans on Information Theory[1]MI-2020(5G)推进组.5G无线技木构架白皮书[上B/Ol2001.47(2):498-519(上接第1483页)克服了二分结构对节点相似性评估的不利影分算法「J.计算机系统应用,2015,24(12):239-243.响;并采用基于共享连接强度的二分密度模块度来衡量网络社[0] Liu xin, Murata t. How does label propagation alyorithm work in bi区结构。该算法经扩展后可应用到二分时序网络,通过挖掘和partite networks[C //Proc of IEEE/WIC/ACM International Joint分析二分网络的社区结构演化过程,跟踪网络演化引起的异质Conference an Web Intelligence and Intelligenl Agent Te hnmlgy节点连接关系的变化和关联热点的迁移.从而把握网络演化白Washington DC: IEEE Computer Society, 2009: 5-8趋势,这也是未来值得进一步研究的内容和方向。[11] Barber M J. Modularity and community detection in bipartite networks[J. Physical Review E, 2007, 76(6): 066102参考文献12 Murata T, Ikeya T. A new modularity for detecting one-to-many cor[1 Zhang Peng, Wang Jinliang, Li Xiajia, et al. Clustering coefficientrespondence of communities in bipartite networks[ J]. Advances inty slnclure of bipartite: nel works J]. Physica A, 2008Complex Systems, 2010, 13(1): 19-317(27):68696875[13]陈伯伦,陈巎,邹盛荣,等,基于矩阼分解的二分网络社区挖据算[2 Llapy M, Magnien C, Vecchio N D. Basic notions for the analysis法[J].计算机科学,2014,41(2):55-58large two-mode networks[ J]. Social Networks, 2008, 30(1): 31-[14] Girvan M, Newman M E.L. Community structure in social and biolog-ical networks[ J. Proceedings of the Natlional Academy of Scie[3 Everett M G, Borgatti s P. The dual-projection approach for two-nces of the United States of America, 2002. 99(12): 7821-7826mode networks[J]. Social Networks, 2013, 35(2): 204-210[15]张聪,沈惠漳,李峰,等.复杂网络中社团结构发现的多分辨率密[4 Zhou Tao, Ren Jie, Medo M, et al. Bipartite network projection and度模决度LJ」.物理学报,2012,61(14):14890201-14890209personal recommendation[J]. Physical Review E,207,76(4):[16]张聪,沈患殪.网络自然密度社因鲒构模块度函数[J].电子科技046115大学学报,2012,41(2):186-191[5」张嬙嬙,黄廷磊,张银眀.基亍聚类分析的二分网络社区挖掘[冂],「Iη陈克寒,韩昐昐,吴健.基于用户聚芡的异构社交闷络推荇算法计算机应用,2015,35(12):3511-3514.[J].计算杌学报,2013,36(2):349-359[6]郭改汶,钱宇华,张晓琴,等,白主确定社区个效的二模网络社区「181 Takahashi d y, SatoW R, FerreiraCe,e!al. Discriminating differ发现算決[J].模式识别与人工智能,2015,28(11):909-975.ent classes of biological nel works by analyzing the graphs spectra dis-[7 Guimera R, Pardo M S, Luis A, ct aL. Module identification in bitribution[J]. Plos one, 2012, 7(12):049949partite and directed networks[ J]. Physical Review E, 2007, 76 (3): [19] Danon L, Diaz-Guilera A, Duch J, et al. Comparing commu036102structure identification[ J] Journal of Statistical Mechanics: The[8」沆华伟,程学旗,陈海强,等.基于信息瓶颈的社区发现[J].计算ory and Experiment, 2005, 2005(9): P09008机学报,2008,31(4):677-686[2u]KoneCtnetworkdataset[eb/ol].(2013-06).http://konect.uni-[9]张弛,周永刚,范纯龙,等,基于信息扩散概率的二分网络社区划koblenz. de/networks/