基于关联系数的社区划分算法

顾宏博，奚杰杰，吴 晶（南京邮电大学 通信与信息工程学院，江苏 南京 210003）

基于关联系数的社区划分算法

顾宏博，奚杰杰，吴 晶
（南京邮电大学 通信与信息工程学院，江苏 南京 210003）

不同于一般社区划分衡量标准——模块度Q值，从社区结构本质出发，提出一种用关联系数评判社区划分好坏的方法，即求社区内部连接与外部连接的关联系数。该方法不但能克服模块度Q值只适用于无向无权网络的缺陷，而且更符合社区结构的定义。

衡量标准；模块度；关联系数；社区结构

0 引言

物以类聚，人以群分。许多社会网络随着时间逐渐演变形成它们自身的社区。它们有一个共同特性——社区结构。整个网络由若干社区构成，每个社区内部节点之间的连接相对紧密，而社区之间的节点连接相对稀疏［1］。

社区划分的研究迄今已有很长历史，学者们已研究出多种划分算法，如GN分裂算法［2］，Newman快速算法［3］、基于Laplace矩阵的谱平分算法［4］、Kernighan-Lin算法［5］等。这些算法有一共性：用模块度量Q［6］作为算法终止条件，同时也作为衡量社区划分好坏的标准。

受Q值启发，衡量标准也可从社区内部连接强度与社区之间连接强度的关联系数出发，能直观地符合社区结构定义［7］，两者的关联系数越小，同时内部连接值越大，之间连接值越小，则划分结果越好。本文利用该思想首先阐述了在划分算法中占重要位置的关联系数，然后提出基于此的算法，最后将算法实验于城市社区划分应用场景，并将本文算法与基于Q值的社区划分算法结果进行比较，结果表明本文提出的算法是切实可行且有效的。

1 社会网络结构相关定义

1.1 社会网络结构

信息图的连接强度矩阵元素Aij表示vi和vj的连接强度，它综合了节点属性、链接属性和共邻属性。

1.2 关联系数定义

设有曲线sin（t）和cos（t），取t=0，1，2，…，10时刻的正、余弦序列｛sin（0），sin（1），…，sin（10）｝，｛cos（0），cos（1），…，cos（10）｝，则两曲线在各t时刻的关联系数如下：其中，Δ（min）和Δ（max）为两曲线在同一时刻对应的最小差和最大差；Δ（t）为两曲线在 t时刻的序列差；ρ为分辨系数，在0～1之间，通常取0.5。

ζ（t）越小，即在t时刻两曲线的关联系数越小，两者相关性越小。

2 基于关联系数的社区划分算法

2.1 算法定义

（1）节点属性

vi和vj属性集为 VAi和VAj，构成带夹角的空间向量，夹角越小表明两节点属性越相似。因此，用夹角余弦计算属性相似度：

（2）链接属性

为与实验数据保持一致，这里用简单的距离dij表示vi和vj的链接属性，并用最大距离 dmax将其归一化：

（3）共邻属性

两节点的共邻数目越多，表明它们的间接联系会越频繁，则划分至同一社区的概率会变大。因此共邻属性为：

（4）连接强度

节点之间连接强度综合考虑三因素：

（5）互信息量NMI［9］

2.2 算法实现

社会网络中节点的连接强度如图1所示，判断两节点能否凝聚至同一社区，需计算社区内部连接强度Inter（ij）和外部连接强度Exter（ij）之间的关联系数。

图1 节点内外连接强度定义

两者的计算公式分别如下：

Inter（ij）表示社区内部连接强度占所有连接强度之比，Exter（ij）表示与社区内部相连的外部连接强度占所有连接强度之比。当Inter（ij）和Exter（ij）关联系数越小，同时Inter（ij）越大、Exter（ij）越小时，表明社区内部的连接强度越大于外部，将该节点对凝聚至同一社区，会使得社区结构越稳定。

Inter（ij）和Exter（ij）关联系数计算公式如下：其中，Δ（ij）=Inter（ij）-Exter（ij）。

基于关联系数的社区划分算法（Community Detection Algorithm Based OnCorrelation Coefficients，CDACC））采用凝聚思想，逐步将社区节点对进行凝聚，具体的处理流程如图2所示。

图2 算法流程

3 实验及分析

（1）数据预处理

获取南京市主城区数据，视各区内的社区为节点，抓取节点属性｛人口、年龄、人均占地面积｝和节点之间距离。

约束条件：以vi为中心，长度D为直径作圆，则在圆形区域内的节点记为vi的邻居节点。

（2）参数选择

式（5）中的参数α、β、γ用单一属性方法获取，即假设认为只有节点属性对社区划分有影响，计算得最优关联系数和ζ1；同理得链接属性和共邻属性的最优关联系数和ζ2、ζ3。ζ越小，表明该属性对社区划分的影响力越大。因此，参数α、β、γ的权重分配为：

由于本文算法是受基于Q的凝聚算法启发，故将本文算法与经典凝聚算法——CNM［10］、凝聚算法的改进CDASW［11］进行比较，并利用互信息量衡量划分结果。

（3）实验分析

首先，用单一属性法得ζ1=3.665 9，ζ2=3.543 4，ζ3=4.328 8。由此看出：在城市社区中，链接属性、节点属性、共邻属性对划分结果影响力依次减小。

利用式（10）得α、β、γ之比，归一化为α=0.347 0，β=0.359 1，γ=0.293 9。将该权重分配与其余4组随机数比较，得到结果如表1所示。

表1 参数比较

因此，在最优参数条件下，将本文算法 CDACC、CNM、CDASW划分结果与真实城市社区结构进行比较，结果如图3所示。

图3 社区划分算法比较

由图3可知，在城市社区中，CDACC、CDASW、CNM算法的划分准确率依次降低，这不仅验证了城市社区的划分需要综合考虑节点属性、链接属性和共邻属性，还证明了CDACC算法的切实可行性。

4 结论

本文针对社区结构发现问题，提出了基于关联系数的社区划分算法。该算法在综合考虑节点属性、链接属性和共邻属性的基础上，计算社区内部和之间的连接强度，并计算两者的关联系数，依次选择关联系数最小的节点对进行凝聚。此外，将该算法实验于城市社区，划分出的社区结构与真实结构相比具有较高的准确性。但是，本文算法复杂度较高，适用于中小型网络。因此，需要进一步探讨算法，减少其复杂度，以便能够适用于各种大型的复杂网络。

［1］郑浩原，黄战.复杂网络社区挖掘——改进的层次聚类算法［J］.微型机与应用，2011，30（16）：85-88.

［2］NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks［J］.Physical Revew E，2004，69（2）：26113.

［3］NEWMAN M E J.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69：06613.

［4］ Ruan Jianhua， Zhang Weixiong.An efficientspectral algorithm for network community discovery and its applications to biological and social networks［C］.Seventh IEEE InternationalConference on DataMining， ICDM 2007，2007：643-648.

［5］ KERNIGHAN B W， LIN S.An efficientheuristic procedure for partitioning graphs［J］.Bell System Technical Journal，1970，49（2）：291-307.

［6］NEWMAN M E J.Modularity and community structure in networks［J］.Proc Natl Acad Sci USA，48109-1040，2006，103（23）：8577-8582.

［7］NEWMAN M E J.Detecting community structure in networks［J］.The European Physical Journal B，2004，38：321-330.

［8］Tang Jin， Jiang Bo， Chang Chinchen， etal.Graph structure analysis based on complex network ［J］.Digital Signal Processing，2012，22（5）：713-725.

［9］ALCOSER，JEFFREY J.Behind our sociality（or social capital）：evolution，the rule of 150，and reading others［J］. Behind our sociality，2014，8（5）：18-25.

［10］CLAUSET A，NEWMAN J，MOORE C.Finding community structure in very large networks［J］.PhysicalReview，2004，70（6）：66-111.

［11］李孝伟，陈福才，刘力雄.一种融合节点与链接属性的社交网络社区划分算法［J］.计算机应用研究，2013，30（5）：1477-1480.

Partition methods based on correlation coefficients for the community structure in social networks

Gu Hongbo，Xi Jiejie，Wu Jing
（School of Telecommunication and Information Engineering，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

Different from general measures of quality standards for the community structure—modularity Q，this paper proposed a new method based on the essence of community structure called correlation coefficients which is the correlation between internal and external links to measure the division.This method can not only overcome the defects of modularity Q which applies only to undirect and unweighted network，but also can be in line with the definition of community structure better.

quality standards；modularity；correlation coefficients；community structure

TP301.6

A

1674-7720（2015）18-0017-03

顾宏博，奚杰杰，吴晶.基于关联系数的社区划分算法［J］.微型机与应用，2015，34（18）：17-19.

2015-03-19）

顾宏博（1990-），通信作者，女，硕士研究生，主要研究方向：社会网络。E-mail：ghb925975754@163.com。

奚杰杰（1990-），男，硕士研究生，主要研究方向：社会网络。

吴晶（1990-），女，硕士研究生，主要研究方向：社会网络。