, 郭静1, 于超11. 东北大学 计算机科学与工程学院，辽宁 沈阳 110169;
2. 东北大学 软件学院，辽宁 沈阳 110169
收稿日期：2017-03-27
基金项目：国家自然科学基金资助项目(61572123，61502092)；国家杰出青年基金资助项目(71325002)；中国博士后科学基金资助项目(2016M591449)；教育部-中国移动科研基金资助项目(MCM20160201)；中央高校基本科研业务费专项资金资助项目(N151604001)。
作者简介：李婕(1982-)，女，辽宁沈阳人，东北大学副教授;
王兴伟(1968-)，男，辽宁盖州人，东北大学教授，博士生导师。
摘要：移动运营商为了拓展新业务，需要增强对用户资源的了解，因此通过大数据分析技术深入分析移动通信系统中的用户行为数据.基于移动通信网络中的用户通话记录提出了一种基于复杂网络聚类算法的用户社交群组构造算法.该算法通过分析用户的通话记录，建立用户间联系紧密度模型.基于局部扩张原理和派系过滤算法进行用户群组构造.鉴于移动通话系统的巨大数据量，采用基于MapReduce编程模型的并行化设计.分别在模拟数据集和中国移动真实数据集下对该算法进行了验证，实验结果表明，该方法具有较好的性能，是可行且有效的.
关键词：移动通信网络联系紧密度群组构造复杂网络MapReduce
Clique Percolation Based Local Fitness Method for User Clustering in Telecommunication Network
LI Jie1, WANG Xing-wei2
, GUO Jing1, YU Chao11. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China;
2. School of Software, Northeastern University, Shenyang 110169, China
Corresponding author: WANG Xing-wei, E-mail: wangxw@mail.neu.edu.cn
Abstract: To expand new business, the telecommunication companies need to understand their users deeply. So the data of the user behavior was analyzed in the telecommunication system by using the big data analyzing technology. A clique percolation based local fitness method was proposed for weighted network algorithm (CLFMw) based on the call logs of users in the telecommunication network. The social relationships were established from all of the call connections. Based on the local fitness method (LFM) and the clique percolation method (CPM), the user group was constructed with CLFMw algorithm. According to the massive data sets of the telecommunication system, parallelization design was used based on the MapReduce programming model. Finally, the group construction algorithm is verified by the simulation data set and the real data set for China Mobile. The experimental results show that this method is well performed but also feasible and effective.
Key Words: telecommunication networksrelationship closenessgroup constructioncomplex networkMapReduce
伴随着移动终端的普及，移动用户数逐渐趋于饱和，各移动运营商竞争越发激烈.移动运营商必须深入了解用户，将更优质的服务提供给用户.构造用户社交群组，并以此来深入了解用户，受到了移动运营商的广泛关注.为此，本文基于移动运营商用户之间的联系紧密度，使用改进的复杂网络中的社区发现方法设计了一套用户社交群组的构造方法.
社区结构的挖掘能够帮助人们发现复杂网络中所隐藏的规律和行为.社区发现算法分为非重叠社区发现算法和重叠社区发现算法[1-2].重叠社区结构更加符合实际情况.目前已有研究者提出了基于派系过滤、线图、局部扩张等重叠社区发现算法[3-9].文献[10]通过引入局部适应度函数提出了著名的LFM(local fitness measure)算法.
LFM算法只需要局部信息而非全网信息即可完成群组的构造，因此该算法非常适合于本文从用户数量较多的基于社交关系的复杂网络中挖掘用户的社交关系群组.然而，LFM主要针对无权网络，并不能直接用于本文所抽象出的有权复杂网络.而且，LFM算法初始时选择节点具有一定的随机性.为了能使该算法有效地适应有权复杂网络中，降低算法的随机性，保证算法运行的质量，本文对LFM算法进行了改进，由于改进后的LFM算法结合了CPM(clique percolation method)算法[11]思想并且可用于处理有权网络，所以将改进后的算法命名为CLFMw(clique percolation based local fitness method for weighted network).
1 问题描述1.1 复杂网络模型将移动通信网络中的用户抽象为节点，用户间的联系紧密度值抽象为边的权值，将用户间的通信关系抽象为有权复杂网络.
1.2 群组构造基于所抽象出的有权复杂网络，改进复杂网络中的优秀社区发现方法作为社交群组构造算法，使其能够应用于本文的有权复杂网络并能适当提高其群组构造的质量.
2 算法设计LFM算法是基于局部扩张原理的经典社区发现算法之一.LFM算法将群组定义为拥有最大局部适应度值的子图，其适应度函数定义为
 | (1) |
LFM算法首先在网络中随机选择一个节点作为种子节点并以该种子节点为初始群组，然后不断向其邻接节点扩张，直至群组的适应度函数fc达到局部最优.随后，算法再次从网络中随机选择一个未被划分至任何群组的节点作为种子节点，迭代执行上述过程，直至所有节点均划分至一个或者多个群组为止.由于各个群组在局部扩张过程中完全独立，相互间无任何影响，因而某一个节点可能同时被划入多个社区，所以该算法能够发现重叠社区.
然而，尽管LFM能够发现重叠社区，但该算法主要针对无权网络，并不能直接用于本文所抽象出的有权复杂网络，所以本文将LFM算法的适应度函数进行了改写，使其适用于有权网络.此外，LFM算法初始时随机选择节点进行群组扩张，这致使该算法具有一定的随机性，且随机选择的节点质量也直接决定着群组构造的结果，并且在实际社交关系网络中，很难定位较好种子节点，即便发现了较好的种子节点，只单一通过一个种子节点作为初始群组进行群组构造也不能得到较好的群组构造效果.鉴于此，CLFMw算法使用种子群组代替种子节点作为算法运行的初始群组.除此之外，CLFMw算法还判断节点是否应该加入群组时的联系度约束条件，并且为防止群组重叠率过高而进行了群组合并.
2.1 联系紧密度计算用户A对用户B的联系强度计算方法如式(2)所示.
 | (2) |
联系稳定性的度量如式(3)所示.
 | (3) |
以A为主体定义A对B的联系紧密度的计算方法如式(4)所示.
 | (4) |
从用户B的角度也可以计算出B对A的联系紧密度IBA，因此定义A与B的综合联系紧密度如式(5)所示.
 | (5) |
2.2 种子群组构造本文在进行群组构造前先构造一个种子群组，种子群组内的节点应为群组内联系非常紧密的用户集合，它们可以作为群组的核心.随后以该种子群组为其他群组构造算法的初始群组，其他群组构造算法在该种子群组的基础上进行群组构造.派系过滤算法是通过全连通子图来构造群组，而全连通子图是网络中节点间联系最为紧密的节点集合，因此其所构造的群组具有较强的群组特性.鉴于此，本文采用基于派系过滤的CPMw算法构造种子群组.为了使构造的种子群组具有层次性，从最大的派系直至最小的派系(2-派系)逐级过滤构造种子群组，算法流程如下.
| 算法1 ?基于非固定派系大小的种子群组构造算法 |
| 输入：有权复杂网络 |
| 输出：种子群组 |
| BEGIN |
| 1：Initialize var k=1 |
| 2：DO |
| 3：??k++ |
| 4：??Calculate satisfied k-clique |
| 5：WHILE k-clique is not the maximum clique |
| 6：WHILE k≥2 |
| 7：??Delete k-cliques that have belonged to other groups |
| 8：??Percolate k-clique |
| 9：??Construct seed groups based on k-clique |
| 10：??k-- |
| 11：END WHILE |
| END |
2.3 适应度函数群组的适应度函数主要用来衡量当前正在构造群组的群组特性，适应度函数越大说明当前群组的群组特性越强.本文将适应度函数定义为
 | (6) |
群组的适应度函数随着邻接节点的加入而不断变化，节点i加入群组后，群组的适应度函数如式(7)所示.
 | (7) |
将上述公式进行变形，可得式(8).
 | (8) |
 | (9) |
2.4 联系度约束联系度约束是为了避免如图 1所示的情况发生，比如用户B只是用户A的一个私人朋友而不应属于群组C.组外的邻接节点除了需要满足该节点的适应度函数大于阈值Fitnodei外，还应满足该节点与群组内的节点的联系边数Nin不小于当前群组内节点总数N的z %，其中z为一阈值.
图 1(Fig. 1)
 | 图 1 错误的群组构造情况Fig.1 Incorrect group construction |
2.5 群组合并定义群组C1与群组C2重叠率InterRate(C1, C2)如式(10)所示.
 | (10) |
2.6 CLFMw算法流程综上所述，CLFMw算法的流程图如下.该算法采用种子节点逐级注入的形式，较大的群组可以通过基于高派系的种子群组进行构造，较小的群组可以通过基于低派系的种子群组进行构造，所以该算法同样能够覆盖网络中所有节点.
| 算法2 ?CLFMw群组构造算法 |
| 输入：有权复杂网络 |
| 输出：群组结构 |
| BEGIN |
| 1: Construct seed groups |
| 2: WHILE existing seed groups not belonging to any groups |
| 3: ??Initialize a seed group which based on largest cliques as initial group |
| 4: ??WHILE current group exists adjacency nodes |
| 5: ??FOR each adjacency node |
| 6:????Calculate Fitnode, Nin |
| 7:????IF Fitnode≥Fitnode* & Nin≥N×z% |
| 8: ?????Add this node into group |
| 9:????END IF |
| 10: ??END FOR |
| 11:?? Calculate InterRate(C1, C2) |
| 12: ??IF InterRate(C1, C2)≥InterRate* |
| 13:?????Merge group C1 and group C2 |
| 14: ????END IF |
| 15:??END WHILE |
| 16: END WHILE |
| END |
3 性能评价3.1 实验平台本文对所设计的CLFMw群组构造方法在Hadoop平台下进行了基于MapReduce的并行实现，并使用LFR基准网络、中国移动真实通话记录数据集分别进行了性能评价.
3.2 并行化设计CLFMw群组构造算法基于局部扩张原理，其基于不同种子群组的各个群组构造部分相互独立、无任何影响，因此可以将各个群组构造过程并行化.为了使CLFMw算法既能高效并行又能同时尽量避免出现大范围的高度重叠的群组，算法采用逐级注入所有基于某一派系的种子群组注入方式.首先将所有基于最大派系生成的种子群组作为CLFMw算法的种子群组并进行并行的群组构造，当群组构造结束，再次将所有基于次大派系的种子群组作为CLFMw算法的种子群组进行并行的群组构造，直至基于2-派系的种子群组注入并群组构造完毕.
3.3 LFR基准网络实验结果分析1) 实验背景.采用基准网络LFR[11].所选取的对比算法为基于标签传播原理的COPRA算法[7]和基于局部扩张原理的OSLOM算法[10]，这两种算法均具有较好的性能[3].采用扩展标准互信息(extended normal mutual information，ENMI)[10]作为性能对比的指标.LFR网络参数参照文献[3]配置，通过分别调整拓扑混合参数μt、权值混合参数μw、重叠节点的个数On来深入观察各个群组构造算法的性能.
2) 拓扑混合参数μt对算法的性能影响.拓扑混合参数μt指节点外部度数占其总度数的比例，设置LFR基准网络中N=50 000，μw=0.1，On=5 000，调整μt，对比结果如图 2所示，CLFMw群组构造算法的性能明显好于对比算法，这主要是因为随着μt不断增大，网络中的群组拓扑开始变得不清晰，CLFMw算法所构造的种子群组具有非常强的群组特性，因此在此情况下性能良好.
图 2(Fig. 2)
 | 图 2 拓扑混合参数对构造群组算法的影响Fig.2 Influence of topological mixing parameters on the group algorithm |
3) 权值混合参数μw对算法性能的影响.权重混合参数μw是节点对群组外节点连接边的权值总和与该节点与所有节点连接边的权值总和的比例值，设置LFR基准网络中N=50 000，μt=0.2，On=5 000，调整μw，结果如图 3所示，随着μw的增大，算法的性能开始出现明显的差异，这主要是因为种子群组在较模糊的群组结构中识别了群组内的核心群组关系，致使其性能好于COPRA算法.
图 3(Fig. 3)
 | 图 3 权值混合参数对构造群组算法的影响Fig.3 Influence of the mixed parameters of weights on the group algorithm |
4) 重叠节点数On对算法性能的影响.重叠节点数On是指基准网络中重叠节点的个数.设置LFR基准网络中N=50 000，μt=0.3，μw=0.2，调整On，结果如图 4所示，CLFMw算法的性能明显好于OSLOM和COPRA算法.这是因为算法初始时所注入的种子群组即有重叠，有利于算法发现重叠群组.而COPRA和OSLOM算法均相当于从一个节点作为初始群组进行群组构造.此外，CLFMw群组构造算法中各个群组构造过程完全独立也是高质量地构造重叠群组的保证.
图 4(Fig. 4)
 | 图 4 重叠节点数对构造群组算法的影响Fig.4 Influence of the number of overlapping nodes on the group algorithm |
3.4 移动通信数据集分析1) 实验背景.实验验证过程中，共度量出4 406 891位用户，33 728 562条有权关系，平均每位用户拥有7.654条关系.图 5为联系紧密度值所对应关系数的分布图，从分布角度而言，联系紧密度值基本符合幂律分布，符合实际情况.
图 5(Fig. 5)
 | 图 5 用户联系紧密度值的关系数分布图Fig.5 Distribution of the number of user relationship tightness |
2) 群组构造质量评估.因为用户的真实群组划分是未知的，所以无法使用标准互信息作为衡量指标，可以采用聚集系数来衡量群组构造的质量.结果如表 1所示，可以看出，各个群组内节点的聚集系数、加权聚集系数的均值都远大于全网所有节点的聚集系数、加权聚集系数，其比值均在4.5倍以上，CLFMw群组构造算法的群组构造质量均较高，算法是可行且有效的.
表 1(Table 1)
 表 1 群组构造算法中聚集系数比较图Table 1 Comparison of clustering coefficients in group construction algorithm
| 表 1 群组构造算法中聚集系数比较图 Table 1 Comparison of clustering coefficients in group construction algorithm | ||||||||||||||||||||||
4 结论本文基于移动用户通话记录设计了一套社交群组构造方法，首先基于通话记录度量了用户间的联系紧密度，然后基于此联系紧密度构建复杂网络，基于局部扩张原理和派系过滤算法设计了群组发现算法，使其能够针对有权复杂网络进行群组构造并保证群组构造的质量.鉴于移动通信网络中的数据量巨大，本文对所改进设计的群组构造算法进行了并行化实现，并对其性能进行了验证.实验结果表明，所设计的群组构造算法具有较好的性能，是可行且有效的.
参考文献
| [1] | 刘大有, 金弟, 何东晓, 等. 复杂网络社区挖掘综述[J].计算机研究与发展, 2013, 50(10): 2140–2154. ( Liu Da-you, Jin Di, He Dong-xiao, et al. Community mining in complex networks[J].Journal of Computer Research and Development, 2013, 50(10): 2140–2154.DOI:10.7544/issn1000-1239.2013.20120357) |
| [2] | Harenberg S, Bello G, Gjeltema L, et al. Community detection in large-scale networks:a survey and empirical evaluation[J].Wiley Interdisciplinary Reviews:Computational Statistics, 2014, 6(6): 426–439.DOI:10.1002/wics.2014.6.issue-6 |
| [3] | Xie J R, 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. |
| [4] | Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J].Nature, 2005, 435(7043): 814–818.DOI:10.1038/nature03607 |
| [5] | Farkas I, ábel D, Palla G, et al. Weighted network modules[J].New Journal of Physics, 2007, 9(6): 180.DOI:10.1088/1367-2630/9/6/180 |
| [6] | Yang X Y, Huang L, Wang K P. Detecting link communities based on hadoop[J].Applied Mechanics and Materials, 2015, 727: 955–958. |
| [7] | Gregory S. Finding overlapping communities in networks by label propagation[J].New Journal of Physics, 2010, 12(10): 103018.DOI:10.1088/1367-2630/12/10/103018 |
| [8] | Deng X L, Wen Y, Chen Y H. Highly efficient epidemic spreading model based LPA threshold community detection method[J].Neurocomputing, 2016, 210: 3–12.DOI:10.1016/j.neucom.2015.10.142 |
| [9] | Chen X L, Han G H, Yuan L, et al.Community detection in multi-dimensional network[C]// IEEE International Symposium on Computational Intelligence and Design.Hangzhou, 2015:598-601. |
| [10] | Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics, 2009, 11(3): 033015.DOI:10.1088/1367-2630/11/3/033015 |
| [11] | Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J].Physical Review E, 2009, 80(1): 016118.DOI:10.1103/PhysRevE.80.016118 |
