陈少权 杜翠凤

【摘 要】针对现有社团发现算法忽略节点之间的关系强度及其动态性的问题，提出改进CPM算法挖掘移动通信的用户关系圈。首先，采用TF-IDF剔除非重要通话群体；然后，引入时间衰减因子，采用用户通信行为衡量用户之间动态关系强度，结合关系阈值剔除节点之间的弱连接构建大小不同的派系；再次，利用变异系数来衡量派系中用户关系之间的相近性，采用变异系数阈值C.V*剔除关系不紧密的派系；最后，根据用户输入的k值，发现k-派系社团。实验证明，通过重叠社团模块度EQ评测指标验证，该算法的精确度高于传统算法的精确度，具有一定的扩展性。

【关键词】关系强度；时间衰减；关系阈值；变异系数

Relationship Mining of Mobile Communication Users Based on Improved CPM

CHEN Shaoquan， DU Cuifeng

[Abstract] In view of that existing association discovery algorithms ignore the relationship strength and dynamic nature， an improved CPM algorithm is proposed for relationship mining of mobile communication users. First， TF-IDF is used to eliminate unimportant communication groups. Then， the time attenuation factor is introduced and user communication behavior is used to measure the dynamic relationship strength between users. The relationship threshold is used to eliminate the weak connections between nodes to construct different factions of different sizes. Thirdly， the variation coefficient is used to measure the similarity between the user relationships in the factions. The variation coefficient threshold C.V* is used to eliminate the factions which are not closely related. Finally， the k- factional community is found on the basis of the k value input by the user. The experiments prove that the accuracy of the algorithm is higher than that of the traditional algorithm by the EQ evaluation index of overlapping community module degree， and it has a certain extensibility.

[Key words]relationship strength； time attenuation； relationship threshold； coefficient of variation

1 引言

移動通信用户关系圈是根据移动用户的通话关系特征、移动用户的行为特征，对移动用户进行社团划分。这种基于用户特征的划分，能够帮助运营商更加了解用户关系网络的构成，为电信业务的拓展提供科学的支撑。当前有不少成熟的社团划分算法，如Palla等人[1]于2005年首先提出了派系过滤算法（CPM，Clique Percolation Method），该算法突破了传统的非重叠社团划分算法的限制，能够用来分析重叠的社团结构，其分析结果更贴近现实的社团结构。由于CPM的计算复杂度较大，Lancichinetti等人[2]于2009年从网络局部结构的角度出发，提出了基于局部扩展思想的重叠社团挖掘算法（LFM， Local Fitness Measure），提升了社团划分的速度。Evans[3]和Ahn[4]等人突破传统以网络节点为研究对象进行网络划分的局限，提出了边聚类的社团划分方法。……