2. 东北大学 软件学院,辽宁 沈阳 110169
2. School of Software, Northeastern University, Shenyang 110169, China
伴随着移动终端的普及,移动用户数逐渐趋于饱和,各移动运营商竞争越发激烈.移动运营商必须深入了解用户,将更优质的服务提供给用户.构造用户社交群组,并以此来深入了解用户,受到了移动运营商的广泛关注.为此,本文基于移动运营商用户之间的联系紧密度,使用改进的复杂网络中的社区发现方法设计了一套用户社交群组的构造方法.
社区结构的挖掘能够帮助人们发现复杂网络中所隐藏的规律和行为.社区发现算法分为非重叠社区发现算法和重叠社区发现算法[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) |
其中:kinc表示群组c内部节点的边数之和;koutc表示群组c的内部节点和外部节点的边数之和;α是一个正实数,用于控制社区的大小.
LFM算法首先在网络中随机选择一个节点作为种子节点并以该种子节点为初始群组,然后不断向其邻接节点扩张,直至群组的适应度函数fc达到局部最优.随后,算法再次从网络中随机选择一个未被划分至任何群组的节点作为种子节点,迭代执行上述过程,直至所有节点均划分至一个或者多个群组为止.由于各个群组在局部扩张过程中完全独立,相互间无任何影响,因而某一个节点可能同时被划入多个社区,所以该算法能够发现重叠社区.
然而,尽管LFM能够发现重叠社区,但该算法主要针对无权网络,并不能直接用于本文所抽象出的有权复杂网络,所以本文将LFM算法的适应度函数进行了改写,使其适用于有权网络.此外,LFM算法初始时随机选择节点进行群组扩张,这致使该算法具有一定的随机性,且随机选择的节点质量也直接决定着群组构造的结果,并且在实际社交关系网络中,很难定位较好种子节点,即便发现了较好的种子节点,只单一通过一个种子节点作为初始群组进行群组构造也不能得到较好的群组构造效果.鉴于此,CLFMw算法使用种子群组代替种子节点作为算法运行的初始群组.除此之外,CLFMw算法还判断节点是否应该加入群组时的联系度约束条件,并且为防止群组重叠率过高而进行了群组合并.
2.1 联系紧密度计算用户A对用户B的联系强度计算方法如式(2)所示.
(2) |
其中:AVGcouple_duration表示A与B的平均通话时长;FREcouple_times表示A与B的总通话次数;AVGall_duration表示A与其所有通话对象的平均通话时长的均值;AVGall_times表示A与其所有通话对象的平均通话次数.
联系稳定性的度量如式(3)所示.
(3) |
其中:FREcouple_weeks_times表示A与B的总通话周数;AVGall_weeks_times表示A与其所有通话对象的平均通话周数;CVgap_weeks表示A与B联系间隔周数的离散系数;AVG_CVgap_weeks表示A与其所有通话对象的联系间隔周的离散系数均值.
以A为主体定义A对B的联系紧密度的计算方法如式(4)所示.
(4) |
其中,θ∈[0, 1],用于调节联系强度与联系稳定性对联系紧密度的影响程度的常量.
从用户B的角度也可以计算出B对A的联系紧密度IBA,因此定义A与B的综合联系紧密度如式(5)所示.
(5) |
其中:nAB表示A主叫B的通话次数;nBA表示B主叫A的通话次数;显然n=nAB+nBA.
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) |
其中:C表示当前正在构造的群组;Bin表示群组内部节点间的边的权值之和;Bout表示群组内部节点与群组外部节点连接边的权值之和;wij表示节点i与节点j连接边的权值;若节点i与节点j间不存在边则wij=0;α为正数常量,可用于调节社区的规模.
群组的适应度函数随着邻接节点的加入而不断变化,节点i加入群组后,群组的适应度函数如式(7)所示.
(7) |
其中:bini表示节点i与群组C内的节点间边的权值之和; bouti表示节点i与群组C之外节点间的边的权值之和.
将上述公式进行变形,可得式(8).
(8) |
定义节点i的适应度函数为节点i加入群组后的群组模块适应度与节点i加入群组前的群组模块适应度差值,即如式(9)所示
(9) |
CLFMw算法将通过计算节点适应度函数Fitnodei的大小是否大于增量阈值Fitnodei决定该节点是否加入当前正在构造的群组.
2.4 联系度约束联系度约束是为了避免如图 1所示的情况发生,比如用户B只是用户A的一个私人朋友而不应属于群组C.组外的邻接节点除了需要满足该节点的适应度函数大于阈值Fitnodei外,还应满足该节点与群组内的节点的联系边数Nin不小于当前群组内节点总数N的z %,其中z为一阈值.
定义群组C1与群组C2重叠率InterRate(C1, C2)如式(10)所示.
(10) |
其中:|C1∩C2|表示群组C1与群组C2交集的节点个数;min(|C1|, |C2|)表示群组C1与群组C2所含节点个数的最小值.当重叠率较大时,重叠的群组极为可能为同一个群组而被重复构造,应该予以合并.设定重叠率阈值InterRate*,如果两个群组间的重叠率InterRate(C1, C2)大于重叠率阈值InterRate*,则将此两个群组进行合并.
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 |