重叠社区与强弱边关系研究

杨红培 刘 萍 王 威

1(许昌电气职业学院 河南 许昌 461000) 2(河南师范大学计算机与信息工程学院 河南 新乡 453000)

重叠社区与强弱边关系研究

杨红培1刘 萍2王 威2

1(许昌电气职业学院 河南 许昌 461000)2(河南师范大学计算机与信息工程学院 河南 新乡 453000)

近年来重叠区域结构的发现使得相对独立的社区关系变得日趋复杂化。对于社区内部以及社区之间的用户关系也变得更加多样性，评估用户关系的紧密程度以及用户关系对信息交流和传播的促进作用已成为目前研究的热点。重叠节点由于自身的特殊性，重叠节点之间以及它们与非重叠节点之间的关系很难用传统的强弱关系进行刻画。针对此问题提出重叠系数指标，以数值形式量化节点之间的强弱关系。在此基础上，对节点度进行重新定义并分析重叠节点与强弱边之间的关系。同时对重叠与非重叠社区结构中强弱边的数量进行了比较分析，发现在重叠社区结构中节点之间隐藏着丰富的隐性关系。最后在对重叠社区结构中弱关系的深入研究发现，移除弱边的过程也是重叠社区结构向非重叠社区结构转化的过程。结果表明重叠结构与非重叠结构并不是相互独立，而是存在着密切联系的，即非重叠社区结构是重叠社区结构网络中的一个特例。

重叠社区结构 重叠节点 重叠系数指标 强弱关系

0 引 言

社区结构的发现有助于人们了解网络中的人际关系，探索网络内部结构的变化情况和预测未来社交网络的发展趋势。社交网络中是强关系重要还是弱关系重要一直是研究的热点。关于强弱关系的评价方法也不断被提出，学者们分别从社交网络结构的不同方面对强弱关系进行了研究，认为弱关系在社交网络中占据着重要的作用[1]。

随着社区发现算法的日益成熟，社交网络中备受关注的问题已经从如何发现网络的社区结构转变为怎样合理有效地评价网络中节点关系的重要性[2-4]。在社区结构发现的基础上，对用户节点之间强弱关系进行判别，并研究他们在信息扩散中的作用，具有理论与现实意义[5]。Pasquale等[6]认为弱关系是远距离传递信息的有效手段，强调了弱关系的作用和重要性。在以社区结构为基础的社交网络，人们普遍认为强关系维持了社区内部节点之间的信息交流，弱关系对社区之间节点交流提供了保障。

重叠社区的发现是对网络社区结构的进一步延伸，它在一定层次上打破了社区个体的封闭性，使得网络中的社区不再孤立，保证了社区之间信息交流的畅通。重叠社区中的节点从属于两个或两个以上的社区，因其自身的特殊性，重叠节点之间、重叠节点与非重叠节点之间的关系很难用强和弱去定义。如图1所示，节点4和节点7属于重叠节点，根据重叠节点归属社区的不同，有以下两种情况：(1) 当把节点4归属于社区1时，那么节点4与节点2、3的关系为强关系，与节点5、7的关系变为弱关系；同理，当把节点4归属于社区2时，那么节点4与节点2、3的关系为弱关系，与节点5、7的关系变为强关系。当节点4为重叠节点时(既属于社区1又属于社区2)，很难用传统的强弱边关系的定义来刻画它与节点2、3、5的关系。(2) 如果只针对重叠社区而言，基于节点4与节点7的关系又可以分为两种情况，即①同为重叠社区，当两个节点同属于一个社区时，它们之间的关系为强关系；②虽然同在重叠社区中，但两个节点又属于两个不同社区，使得它们之间的强弱关系也很难下定论。

图1 重叠社区结构图

针对该问题，本文提出了重叠系数指标，在重叠社区结构的基础上，对网络中的节点关系以权值的形式重新定义，使得强弱关系可量化。本文的主要贡献如下：

(1) 基于四个数据集，在划分重叠社区结构的基础上，提出了重叠系数指标，以此为基准，判断重叠社区结构下节点之间的强弱关系。

(2) 对节点度进行了重新定义。在具有重叠区域结构的网络中，根据重叠社区系数指标，对节点之间的权值进行重新定义，构建重叠社区结构关系网络，挖掘节点之间隐藏的社会关系。

(3) 分析了重叠节点与强弱边之间的关系，发现重叠节点是连接社区内部与外部进行通信的桥梁。

(4) 对重叠与非重叠两种网络结构下的强弱边数量进行对比，发现在重叠社区结构中强弱边数量要明显高于非重叠社区结构下，进一步阐述了重叠社区结构下隐藏的节点关系。

1 相关工作

随着网络技术的进步，网络中社区结构的研究成为越来越重要的一个热点问题，社区发现和检测算法获得较快发展并且日益成熟。

2002年，Girvan等提出了GN算法，是一种经典的社区发现算法。该算法属于分裂型，在算法执行过程中计算所有边的边介数，并依次删除边介数最大的边，最终实现网络社区结构的划分，同时这种方法启发了人们对网络社区研究的思路[7]。2004年，他们又提出了网络划分指标函数——模块度Q，模块度值的大小主要取决于网络中节点所属社区的分配情况，对于衡量社区划分的精确度是一个重要参考指标[8]。2007年，Zhang等[9]以特征矩阵作为原始输入，提出了NMF算法，检测到网络中存在着一个节点可能同时属于多个社区的情况。2011年，Psorakis等[10]在NMF算法的基础上，提出了基于贝叶斯的NMF算法。从网络中提取出具有重叠区域的模块，并且通过利用模块度量化指标对所划分的社区精确程度进行合理性评价，最终实现对网络社区中重叠结构的划分。2014年，李玉翔等[11]在BNMF算法的基础上进一步改进，通过对NMF算法的研究分析，对原始输入的特征矩阵进行相关扩展性处理，可以有效地统计出网络中社区数目。并在此基础上利用节点与社区之间的所属关系，实现对节点的划分。2006年，Shi等深入研究了关系网络的连通性，并在此基础上，发现在健壮的社交网络中存在着薄弱环节。这些薄弱环节的存在延长了网络中的平均最短路径，通过对网络中信息传递关系的研究，发现删除网络中的弱连接会隔离网络中绝大多数的节点[1]。2007年，Onnela等[12]提出了网络结构的概念，深入研究了移动机会网络结构与节点关系强度之间的联系，认为网络完整性的保持需要以牢固的关系为基础，提出在通信网络中移除弱关系的结果可能会导致在一个阶段上的网络崩溃。虽然紧密联系的强关系被去除对于网络信息传输影响不大，但是会影响到网络信息传输的整体完整性。Yang等在2012年-2013年提出一个基于集群关系模型的社区检测算法用于检测重叠社区的密度，较为精确地发现网络中真实的重叠社区结构。对网络重叠社区内外部节点之间的紧密关系进行了研究，根据重叠社区中节点关系的密集程度，重叠社区可进一步划分为稀疏和稠密重叠社区两种类型[13-14]。2014年，Pasquale等[6]提出了一种只依赖于社交网络拓扑结构的强弱关系定义方法，找到适用于Facebook的全新弱关系定义。通过研究强弱关系对信息传播过程的影响，强调了弱关系的作用和重要性。在社区发现的基础上，关于强弱关系在整个大型网络中所起到的作用一直是研究人员重点关注的一个问题。

随着重叠区域结构的发现[15]使得相对独立的社区关系复杂化，对于社区内部以及社区之间的用户关系也变得更加多样性，用户之间的强弱关系也变得愈加不确定。人们在复杂网络中判断强弱关系时，没有更多地考虑到重叠社区结构的特性，由于重叠社区的普遍存在，重叠社区与非重叠社区中节点之间的强弱关系情况难以定义。针对该问题，本文在发现重叠社区的基础上提出了重叠社区指数作为划分节点关系的一个参考指标。

2 重叠系数指标

本节中提出了重叠系数指标作为评价节点强弱关系的一个参考指标，即从社区与重叠社区相结合的角度来观察节点之间的关系，以关系权值的方式表示节点之间的关系强度，可以使得复杂的网络关系简单化。重叠系数如下式：

(1)

式中：Ei和Ej表示节点i和节点j所归属的社区，Ei∩Ej表示节点i、j共同拥有的社区数量，Ei∪Ej表示节点i、j所属社区的并集。Oij表示节点i与j之间的关系权值。

图2 重叠系数指标计算图例

重叠系数指标的提出，以权值的方式解释了网络中的复杂关系，使其关系可量化。同时以关系权值的表示形式解决了第1节提到的2种难以界定的节点关系。通过对节点关系的数值化处理有利于把复杂的网络关系归一化，在一定程度上简化了网络结构的复杂度，以数据标识的方式增加了人们的认知度。

图3展示了4个数据集以重叠系数赋予节点之间新的权值所生成的邻接矩阵(这里截取部分行、列)。从图中可以看到，节点之间的关系权值由0到1，同时也由简单到复杂再回归到简单的一个过程。

图3 四个数据集新的权值邻接矩阵图

3 节点度

在图论中，节点度是指和当前节点相连接边的总条数，节点度的大小可以直接反应出当前的节点在整个网络中的重要程度，便于对节点的重要性做出一个初步的评断。根据网络中节点之间的连接情况，建立相应的邻接矩阵，可以快速地统计网络中每个节点的节点度。

(2)

式中：xij表示邻接矩阵W的第i行第j列的元素权值，Di表示当前节点i的节点度。由于在图论中，节点图可以划分有向图和无向图，对于有向图来说，节点度又可以划分为入度(表示网络图中指向该节点的边的集合)和出度(表示从该节点出发的边的集合)。

图4展示是6个节点形成的有向拓扑图，以节点5为例，来计算出节点5的出度和入度如下：

(3)

(4)

图4 有向拓扑图

图4中以节点5为出发点，因为发出的边分别与节点1、2、4相连，所以节点5的出度为3，相应计算得到它的入度为2。

对于无向图来说，节点度的统计要简单得多，以当前节点是否有连接边为标准，在统计过程中进行累加，最后得到无向图中节点度，运算如式(1)。

无论是有向图还是无向图，如果节点的节点度越大，就表明该节点周围密度较大，同时也说明了该节点在网络局部中所起的作用越重要[15]。对于网络中信息流动来说，节点之间如果有连接边，表明信息在这两个节点之间是可以传输信息，连接边越多，信息传递时稳定性越好，也可以说明当前节点对网络中的信息扩散影响就越大，对网络信息传输的畅通性就越有保障。

从关系权值的角度进一步分析发现，在原始的大型网络中，根据4个数据集中节点的原始关系生成由0和1组成的邻接矩阵，0、1表示节点之间关系的权值。这种权值的表示方法具有“二分性”，邻接矩阵展示出了节点之间的绝对关系，把用户分为绝对的联系和无联系。然而在真实的世界中绝对的事情大多是不存在的，因为在现实世界中很多事物之间看似没有任何关系，但其中却总是隐藏着或多或少的联系。随着重叠社区结构的出现，网络中所隐藏的关系逐渐被暴露出来，网络结构变得越来越复杂。

第2节提出的重叠系数指标，就是在基于重叠结构的社区中，根据重叠社区的特殊性，在社区的层次上重新定义节点之间的关系权值。本节以统计每个节点的节点度为基础，对非重叠和重叠社区结构网络进行比较。

(5)

式中：xij表示节点之间的关系权值。

图5、图6为基于PCA算法和NMF算法的两种数值比较。其中横坐标表示节点ID，首先对非重叠社区结构中所有节点度进行升序排列，并以此序列作为横坐标；纵坐标表示节点度。

图5 基于PCA算法节点度对比图

图6 基于NMF算法节点度对比图

在具有重叠区域结构的网络中，根据重叠社区系数指标，对节点之间的权值进行重新定义。构建重叠社区结构关系网络，按照节点度的统计方式计算出在重叠社区结构网络中每个节点的数值。

初始网络中节点之间的关系权重为0或1，根据节点关系建立的0、1邻接矩阵，每一行元素值之和就是与当前节点相连接的所有节点的边权值总和，据此得到当前节点i节点度。根据节点度的大小对当前网络中节点进行升序排列，如图5和图6中逐渐上升的曲线展示了对原始网络节点的权值排序结果。

在原始网络中本来没有直接关系的两个节点，根据重叠系数指标重新给节点关系赋以权值使得节点之间所隐藏的关系显露出来。此时部分节点之间边的权值已不再是0，说明这些节点之间建立起来了或多或少的联系。根据两种权值情况下的实验结果发现，在重叠社区结构情况下节点的数值普遍较高，这是因为在具有重叠社区的社交网络中，使得节点之间的潜在联系显现出来。此时节点之间的关系不在具有绝对的二分性，而更多地体现了现实世界中关系的普遍性。

从图5与图6中的波折曲线可以看到，在具有重叠区域结构的网络中，绝大多数节点度要大于原始网络节点度。实验结果表明：① 重叠社区的存在明显地改变了节点关系的判断标准；② 重叠结构的存在挖掘出了节点之间隐藏的关系，加强了节点之间的联系，完善了复杂网络的关系结构，同时也使得节点之间所构成的无向图更加紧密。

4 重叠节点与强弱边之间的关系

重叠节点的发现与存在有着它独特的一面，它处于多个社区相互重叠的区域，构成了社区之间信息传输的桥梁。重叠社区的形成是由属于多个社区的节点所组成的一片区域，使得在非重叠社区结构中只能依靠弱连接维持信息传递的关系多了一层保护，确保了社区之间信息交流的畅通。

本节以重叠社区为基础，以重叠节点为研究对象，按照一定比例依次把重叠节点移到非重叠社区中。同时应用PCA和NMF两种算法分别对相关节点的强弱边进行统计，并观察网络中的强弱边数量的变化情况。

由PCA和NMF两种算法统计结果得知，随着重叠节点逐渐被移到非重叠社区，网络中强弱边的数量都在快速的增加，并最终随着重叠社区中节点完全被移出，强弱边的数量也达到峰值。同时也可以看到重叠节点逐渐被移出的过程，就是重叠社区结构向非重叠社区结构转变的过程。当重叠节点完全被移出时，非重叠社区结构则正式形成，网络中出现信息孤岛现象。

进一步分析可知，在开始阶段，随着重叠节点的递减，强弱边数量出现了一个明显的上升趋势，这说明了重叠社区中的节点在强弱连接中起着一个非常大的支撑作用，重叠社区的出现为信息扩散起到了巨大的保证作用。在后半段，弱边数量的增长速度要显著高于强边的数量，这说明了随着重叠节点的不断减少，弱连接成为网络关系中的主体，弱关系逐渐发挥出在信息传输方面的优势。

实验结果表明，重叠社区的出现削弱了社区内部节点之间的强联系，重叠部分构成了社区内外连接的桥梁，在社区内部与外部之间起到一个过渡的作用。重叠区域结构的存在使得社区内部与外部的区分不是非常明显，让信息的传输交流不至于因为强边或弱边的消失而导致中断，在整个网络社区的信息传输中起着重要的作用，有助于保证信息的畅通性。

5 两种网络拓扑中强弱边数量比较

考虑到重叠社区结构在社交网络中的广泛存在性，在讨论强边和弱边时，就不能抛开重叠社区来主观地区分强弱关系。针对该问题，根据第2节提出的重叠系数指标Oij，对重叠社区结构中节点之间的复杂关系以权值的形式进行定义，以数字的形式把复杂关系简单化。

考虑到节点之间关系的强弱由边的权值来决定，定义阈值μ，把μ=0.5作为强弱关系变化的一个分界线，当Oij>0.5时表示节点i和j之间为强连接，当Oij≤0.5时表示节点i和j之间为弱连接。

基于PCA算法和NMF算法对重叠社区结构和非重叠社区结构网络中的强弱边数量进行统计，在重叠社区结构中根据重叠系数指标统计出的强弱边数量要明显高于非重叠社区结构中的强弱边数量。该现象充分说明重叠系数指标充分挖掘出了节点之间的潜在联系，更深层地反映了真实世界网络的内部特征。

6 结 语

为解决重叠社区结构下节点之间强弱关系的不确定性，本文提出了重叠系数指标，给节点之间定义新的关系权值，并从节点度的角度对重叠社区结构和非重叠社区结构进行实验对比。接着通过改变重叠社区中重叠节点的比例，观察网络中强弱边的变化情况，来进一步验证重叠社区的重要性。同时发现移除弱边的过程也是重叠社区结构向非重叠社区结构转化的过程。最后对两种社区结构中强弱边数量进行统计比较，发现在重叠社区结构中节点之间隐藏着大量的关系，这些隐藏的关系对网络信息交流的畅通起到了有力的保障。

[1] Shi X,Adamic L A,Strauss M J.Networks of strong ties[J].Physica A Statistical Mechanics & Its Applications,2006,378(1):33-47.

[2] Xie J,Kelley S,Szymanski B K.Overlapping community detection in networks:The state-of-the-art and comparative study[J].Acm computing surveys,2013,45(4):43.

[3] Yang J,Leskovec J.Overlapping Communities Explain Core-Periphery Organization of Networks[J].Proceedings of the IEEE,2014,102(12):1892-1902.

[4] Meligy A,Samak A H,Saad M E.A new Pre-processing Strategy for Improving Community Detection Algorithms[J].International Journal of Computer Applications,2015,119(16).

[5] Zhao J,Wu J,Xu K.Weak ties:Subtle role of information diffusion in online social networks[J].Physical Review E,2010,82(1):016105.

[6] Meo P D,Ferrara E,Fiumara G,et al.On Facebook,most ties are weak[J].Communications of the Acm,2012,57(11):78-84.

[7] Girvan M,Newman M E J.Community structure in social and biological networks[J].PNAS,2002,99(12):7821-7826.

[8] Newman M E J.Analysis of weighted networks[J].Physical Review E,2004,70(5):056131.

[9] Zhang S,Wang R S,Zhang X S.Uncovering fuzzy community structure in complex networks[J].Physical Review E,2007,76(4):70-80.

[10] Psorakis I,Roberts S,Ebden M,et al.Overlapping community detection using Bayesian non-negative matrix factorization[J].Physical Review E,2011,83(6):1509-1520.

[11] 李玉翔,李弼程,郭志刚.基于非负矩阵分解的网络重叠社区发现研究[J].系统仿真学报,2014,26(3):643-649.

[12] Onnela J P,Saramäki J, Hyvönen J,et al.Structure and tie strengths in mobile communication networks[J].Proceedings of the National Academy of Sciences,2007,104(18):7332-7336.

[13] Yang J,Leskovec J.Community-Affiliation Graph Model for Overlapping Network Community Detection[C]//IEEE,International Conference on Data Mining.IEEE Computer Society,2012:1170-1175.

[14] Yang J,Leskovec J.Overlapping community detection at scale:a nonnegative matrix factorization approach[C]//Proceedings of the 6th ACM international conference on Web search and data mining,2013:587-596.

[15] 胡丽莹,郭躬德,马昌凤.基于对称非负矩阵分解的重叠社区发现方法[J].计算机应用,2015,35(10):2742-2746.

RESEARCHONTHERELATIONSHIPBETWEENOVERLAPPINGAREAANDSTRONG-WEAKEDGES

Yang Hongpei1Liu Ping2Wang Wei2

1(XuchangElectricalVocationalCollege,Xuchang461000,Henan,China)2(CollegeofComputerandInformationEngineering,HenanNormalUniversity,Xinxiang453000,Henan,China)

In recent years, the discovery of overlapping regional structures has made the relatively independent community relations become more and more complicated and the user relationship between the community and the users also have been more diversity. It is a hot research to evaluate the tightness of user relations and the promotion of user relations to information exchange and communication. Overlapping nodes the overlap between the nodes and their relations with non-overlapping between nodes is hard to be described by using the traditional strength of the relationship, because of its particularity. In this thesis, we proposed overlap coefficient index between nodes in the strength of the relationship between the quantitative numerical forms to solve this problem. On this basis, we redefined the nodes and analysis of the relationship between the overlapping nodes and the strength of the edge, the number of overlapping and non-overlapping community structure of strong and weak edge. We found a hidden relationship between the hidden nodes in the rich overlapping community structure; finally found there are plentiful weak relationships in deep research of the overlapping community structure, in the process of remove the weak edge and overlapping community structure to process non overlapping community structure transformation. The results showed that the overlapping structure and non-overlapping structure were not mutually independent, but closely related, namely non overlapping community structure is a special case of overlapping community structure in the network.

Overlapping area structure Overlapping nodes Overlapping coefficient index Strong-weak relationship

2017-02-13。国家自然科学基金项目(U1404602)。杨红培，讲师，主研领域：计算机网络通信，软件教学及研究。刘萍，工程师。王威，硕士生。

TP3 TP393.0

A

10.3969/j.issn.1000-386x.2017.11.028