《一种大规模呼叫图最大团发现算法p125130》由会员分享，可在线阅读，更多相关《一种大规模呼叫图最大团发现算法p125130（6页珍藏版）》请在金锄头文库上搜索。
1、一种大规模呼叫图最大团发现算法水 吴斌王柏苏雪峰 w u b i n b u p t e d u c a 北京邮电大学计算机科学与技术学院1 0 0 8 7 6 摘要：呼叫图是由呼叫号码与呼叫联系组成的一个图。大规模呼叫图构成了一个复杂网络结构。而复 杂网络的研究正成为多个学科的热门研究领域。本文研究了大规模呼叫图的基本特征，证实其与互联网结 构等无尺度网络一样满足幂律等特性。在此基础上，提出一种针对大规模呼叫图的最大团发现算法M C T 。 算法的特点在于利用幂律特性，以三角关系为最大团的分析基础，缩小了候选结点集，并通过排序和剪技 策略，算法能较快找到最大团。实验结果表明，相对一般的最大团
2、算法，针对大规模呼叫图M C T 算法的 效率提高了一个数量级。 关键字：最大团幂律复杂网络呼叫图客户关系管理 F i n d i n gM a x i m u mC l i q u ei naM a s s i v eC a l lG r a p h A b s t r a c tA c a l lg r a p hi sag r a p hw i t hv e r t i c e sb e i n gt e l e p h o n en u m b e r sa n de d g e sc a l l sm a d ef r o mo n e n u m b e rt oa n o t h
3、 e r C l i q u e si nt h ec a l lg r a p hr e p r e s e n ti m p o r t a n ts t r u c t u r a li n f o r m a t i o n I nt h i sp a p e r , w ep r e s e n ta m e t h o do ff i n d i n gm a x i m a lc l i q u ef r o mam a s s i v ec a l lg r a p h F i r s t l y , w eh a v es t u d i e dt h ep o w e rl
4、 a wp r o p e r t yo f t h em a s s i v es p a r s eg m p h ，w h i c hi so n ek i n do fs c a l ef r e en e t w o r k s ；t h e n ，an o v e lM a x i m u mC l i q u ea l g o r i t h mw i t h t h ev e r t e xo r d e rt a k e nf r o ma p p e a r i n gt i m e si nT r i a d s ( M C T ) i sp r e s e n t e
5、d I ti sb a s e do nt h en e w l yf a s t b r a n c h - a n d - b o u n da l g o r i t h m sf o rt h em a x i m u mc l i q u ep r o b l e m E x p e r i m e n t a lr e s u l t ss h o wt h a ti to u t p e r f o r m st h e o r i g i n a la l g o r i t h m sf o rt h em a s s i v ec a l lg r a p hb ys c
6、a l i n gd o w nt h ec a n d i d a t es e t T h ee m p i r i c a ld a t a s e t sw eu s e d a r ef r o maC u s t o m e rR e l a t i o n s h i pM a n a g e m e n t ( C R M ) d a t aw a r e h o u s eo f am o b i l et e l e c o mc o m p a n y K e y w o r d s ：m a x i m u mc l i q u ep o w e rl a wc o m
7、 p l e xn e t w o r k s c a l lg r a p h 1 、引言 由于复杂网络在宇宙中无处不在，复杂网络已经引起从基础学科数学、物理学到应用学 科生物学、医学、计算机科学乃至人文学科中的社会学以及前沿交叉学科复杂性科学等多学 科的越来越多的研究人员的关注 1 - 4 ，1 1 - 1 2 。在电信领域，由用户的通话详单获得的用户 呼叫图在一定的时空条件下构成了一个复杂网络。呼叫图的结点为用户号码，边表示为用户 间进行过通话。在一个地区、城市、省的地域范围内，一天、一个月的呼叫图形成了一个大 规模呼叫图，同时也是一个复杂网络。研究这样一个复杂网络的特征，不仅是继组织代
8、谢网 络、互联网、蛋白质调控网络、科研合作网络、沟通网络、词汇网络等之后又一个复杂网络 实例的分析，而且通过用户群体关系结构的发现，可以为相关的社会网络分析、客户关系管 理等提供实用性的知识。 本文研究了大规模呼叫图的特征，用实例证明移动通信网络中用户呼叫图满足幂律分布 特征，并获得呼叫图中构成极大团的结点数的幂律分布特征，由此，提出了一种针对大规模 呼叫图的最大团发现算法M C T 。此算法利用幂律分布特征，将以往的最大团求解以结点度为 + 本课题得到国家自然科学基金( 6 0 4 0 2 0 1 1 ) 资助 基础提升到三角关系集，由于候选结点集程幂指数的削减，再结合基于三角关系集进行结点
9、 排序和剪枝策略，算法M C T 获得了比一般以边( 二元) 关系为基础采用分枝定界等方法的同 类算法较高的效率。实验证明了这一结论。因为团结构在社会网络中有着重要的意义，本文 定义了呼叫图结点的团值，即结点所在的最大团的大小。基于最大团发现算法，将用户的团 值与其基本属性关联分析，提出并证实了一个客户忠诚度假设：团值越大，用户忠诚度及价 值越高。此假设为客户关系管理中客户细分提供了一条有用的知识。 论文组织如下：第2 节介绍呼叫图的特征分析；第3 = 肖重点描述针对大规模呼叫图的最 大团发现算法M C F ，详细分析算法的两个组织部分；第4 节是实验结果及分析，以及分析算 法的实用性，即对用
10、户忠诚度假设进行实验分析；本文最后是总结和进一步研究工作的介绍。 由于篇幅所限相关研究工作介绍从略。 2 、呼叫图的幂律特征 首先说明本文涉及的基本概念和使用的符号。一个图G ( V ，昱) ，由一组结点集y 和一 组边集E 组成。如果( 1 _ ，w ) E 则结点v ，W 为相邻结点。对于图中一个结点V ，r ( v ) 表示 与它相邻的结点集合，旷( V ) l 则为结点y 的度反。如果一组结点Q c _ G 且对于所有 v ，W Qv W ，都有( V ，w ) E ，结点集Q 及相应边构成的子图Q 称为团( c l i q u e ) ，团 的大小占= l Q l 。对于一个图G (
11、 y ，E ) ，所有团中最大的团称为最大团，用E 表示最大团 的大小。c o ( v ) 表示包含结点v 的最大团。对于图G ( V ，E ) 中的一个团Q ，其结点集为Q ， 如果不存在结点v V Q ，使得V 与Q 中所有结点相邻，则称团Q 为极大团。- 跑( 占) 表示 所有大小为占的团的集合，V s q ( 占) 表示组成S Q ( e ) 的结点集。 下面说明呼叫图的幂律特征。呼叫图数据来源于某省一个地市某个运营商一个移动通信 网一个月的通话详单。结点由通话号码组成，边表示呼叫联系。忽略主被叫和通话次数等数 据，即将详单处理为一个无权无向图。它的结点数为5 3 4 0 0 4 ，边
12、数为1 0 3 0 0 2 7 。图卜2 表示了 这个图的统计特征。图l 是呼叫图的度的分布图。横轴表示度值d 的对数，纵轴表示度值为d 结点数的对数。蓝色表示原始数据的分布曲线，红色表示线性回归分析的曲线，口= 2 3 9 。 若设结点所在最大团为该结点的团值，图2 表示结点团值的分布。横轴表示团值占的对数， 纵轴表示团值为占结点数的对数。蓝色表示原始数据的分布曲线，红色表示线性回归分析的 曲线，口= 5 0 2 。图3 表示团的分布。它来源于地域范围为一个省的呼叫图，结点数为 2 4 1 2 9 1 1 ，边数为5 2 8 5 2 0 8 。横轴表示团的数量( 百万为单位) ，纵轴表示团的
13、大小。由于图 3 中所选取的团不仅包括极大团还包括大团分解的小团，所以图3 出现了中间的高峰。从图3 中还可以看到一个数百万结点的呼叫图其最大团大小只有2 6 。 1 2 6 图l 度分布图2 团结点分布 图3 团分布 3 、最大团发现算法M C T 基于上一节对呼叫图的静态统计特征的分析，本文提出种基于三角关系的针对复杂网 络的最大团发现算、法M C T ( M a x i m a lC l i q u ea l g o r i t h mb a s e do nT r i a d s ) 。篇幅所限M C T 算法的具体描述从略。 M C T 算法分为两个部分，第一部分求图的三角关系，用T
14、 r i _ c l i q u e - 子算法实现，子算法 过程比较简单，就是找结点( 若A ) 的邻接结点集中所有两两相邻的结点( 若B ，C ) ，则( A ， B ，C ) 为三角关系集中一个三元组。由于相对于数百万的结点数，每个结点邻接表的长度著 不大，可以发现这一过程主要时间消耗并不是两个邻接表的比对，而是确定需要比对邻接表 的位置，因此，本文选用了邻接表表示呼叫图，并配合哈希表，使得这个过程有较理想的时 间复杂度。 由于T i i _ c l i q u e 子算法的关键性，下面大致分析一下7 H c l i q u e 子算法的时间复杂性。 设2 为呼叫图的结点数，m 边数(
15、I S Q ( 2 ) 1 ) ，哈希表的长度为k ，采用邻接表处理冲突， 成功定位某个结点( 邻接表) 的平均时间为l + 2 ( k 宰2 ) ，两个邻接表比对时间约为 O ( ( 聊力2 ) ，T r i _ C l i q u e 子算法的时f q 复杂度约为( 1 + n ( k 宰2 ) + ( m 疗) 2 ) 宰聍因为 ，z m n ，所以适当选取七，T r i 予算法的时间复杂不会高于线性复杂度。由于Clique 行t c l i q u e 子算法是M C T 算法的重要部分，它的高效将直接提高b i C T 算法的效率。 M C T 算法的第二部分是基于三角关系组，计算最
16、大团。在得到三角关系组S Q ( 3 ) 以后， 对构成三角关系的结点集V s q ( 3 ) 按照它在蹭( 3 ) 第位出现的次数T r iL e n 删序，依照 降序将对于第一位都为的三元组去掉，交换为二元组S Q ( 2 ) j ，以这个子图为输入，采 用F A S T 算法【6 】或者M C Q 算法【7 】包括v t 求最大团国) ，这样得到若千极大团，其中最大的 就是最大团。F A S T 算法和M C Q 算法是近年出现的比较高效的针对标准集求解最大团的算 法。算法详细的说明参见相关文献。F A S T 算法是一种基本的分支界定计算最大团的算法， M C Q 是一种相对F a S t 而言快速的最大团发现算法，它是一种染色十剪枝快速发现团的方法。 总的来说，这两种方法都是在一些小规模数据( 标准数据集) 上进行实验和比较，实验发现 对于海量的电信数据，它们在时间和空间方面性能都有所下降。M C T 算法不必计算所有结 1 2 7 点的最大团，当包含v 的三元组数小于| Q m a x I
