电信网络链接稳定性模型研究

郭 喆，王芙蓉，黄本雄

(华中科技大学电子与信息工程系，湖北 武汉 430074)

随着通信技术的不断发展，通信网络已经深入到人们的日常生活中。根据工信部2010年3月的统计数据［1］，我国目前固定电话用户有3．1亿户，移动电话用户有7．7亿户。研究用户行为对网络规划和优化，客户关系管理，市场营销等方面有重要意义。电信用户行为主要指用户的通信行为，包括通信的时间、对象、地点和应用何种业务等。用户行为能够刻画用户的特征，从底层协议设计到各种电信应用服务都与用户的行为具有紧密的联系。文献［2－4］对移动用户的移动性进行了研究，指出用户的移动性符合幂率分布，移动用户的运动有很强的规律性，其移动性在很大程度上是可预测的。文献［5］从社会网络的角度研究人们的谈话内容以确定其社会属性。文献［6］研究了电信用户通话时长规律，发现电信用户的通话时长符合对数正态分布或多个对数正态分布的加权和。以上研究从通信的时间和地点等方面对用户行为进行了分析和建模，为进一步挖掘用户特征提供了重要特征数据和结论。

研究用户的行为不得不考虑用户之间的相互影响，为更方便准确地描述用户之间的联系和影响，可以将电信用户看作社会网络中的实体，用户之间的通信看作点与点之间的链接。社会网络具有动态性，表现在随时间推移有新的实体和链接加入，旧的实体和链接消失，这一点与通信网络的特点也非常相符。社会网络的链接挖掘近年成为研究的一个热点。文献［7］对链接挖掘作了综述性介绍。对于链接的研究主要有两方面，一方面是推测哪些实体在未来可能产生新链接，也就是链接预测问题。文献［8］提出邻近度的方法，文献［9］用关系马尔科夫网络(RMN)进行链接预测，文献［10］比较了各种预测方法，文献［11］用统计关系学习对链接预测进行建模。另一方面是链接的稳定性预测，这是链接挖掘中一个新的课题。链接的稳定性预测指的是对当前时间窗口内已经存在的链接进行稳定性评价，以预测在下一时间窗口该链接是否会消失。在通信网络中，稳定性预测更有实用意义，例如可以预测用户流失，或者进行精确有效的业务推荐等，此外，对于网络资源分配优化，用户关系管理等方面也有帮助。

笔者对电信网络链接的稳定性进行了研究，建立链接稳定性预测模型，并提出一种基于链接权重和节点度的评价方法。通过在大型通信网络中的检验，该方法具有很高的准确性。

1 链接预测方法

用一个无向图G=＜V，E＞来表示社会网络，V为顶点集合，E为边集合。链接相当于边e(u，v)∈E，其中 u，v为边 e的两个顶点，u，v∈V。对于两个不同的时间 t＜t'，子图 G［t，t'］包含在该时间内所有出现过的边，其集合为E［t，t'］。链接预测的问题是对4个不同的时间t0＜t1＜t2＜t3，由某种预测算法能够得出在子图 G［t2，t3］中存在，在子图G［t0，t1］中不存在的边，即预测会新出现哪些边。为便于理解和计算，所有的预测方法都可以看作是一种打分方法，即对每一条不存在的边进行打分，得分越高则在将来这条边出现的可能性越大。

1．1 基于共邻点的方法

对于一个节点x，用Г(x)来表示x的邻节点集合。在一般情况下，两个并不直接相连的节点x，y，如果有很多相同的邻节点，那么它们之间在将来可能出现链接。最简单的打分方法就是看它们之间重合的邻居节点个数，即:

1．2 索尔顿指数

索尔顿指数定义如下:

式中，k(x)为节点x的度(x邻居节点个数)。

1．3 雅克比指数

该指数是由雅克比在100多年前提出来的，其定义如下:

1．4 索伦森指数

该指数通常使用在生态学领域，其定义如下:

1．5 Adamic－Adar指数

这种计算方法是在单纯计数共同邻居节点个数的基础上加入了权重的概念，对于两个节点的共有邻居节点，如果度越小，则这种邻居节点具有专一性，从而获得较高的权重，这种专一的共同邻居节点越多得分越高［12］。其定义如下:

1．6 择优联结

择优联结的机制可用于自由尺度网络的演化(例如按照幂律分布的网络)［13］，节点x的一个新链接产生概率正比于该节点的度k(x)，那么两个节点之间产生新链接的评分标志为:

1．7 卡茨指数

这是一种基于全路径的方法，该方法找出节点x与y之间所有的路径，对每一条路径进行一次评分，然后相加。路径越短评分越高，表示为:

1．8 SimRank

SimRank使用一种递归算法来计算两个节点之间的相似度，并以此相似度作为两节点的打分，其定义如下:

其中，sxx=1，γ∈［0，1］。SimRank也可以表述为一种随机游走模型，即两个节点之间的相似度为γl。其中，l为一随机变量，表示任意时刻从节点x随机游走到节点y的步数。

上述方法基本上分为两类，一类是基于共同邻节点的方法(即前6种方法)，一类为基于路径的方法(即后两种方法)。基于路径的方法往往需要获得全网络的拓扑结构，计算全路径需要很大的计算量，在实际应用中受到很多限制，但其准确性较高。基于共同邻节点的方法所需要的信息不多，计算量也不大，应用更为广泛。对于链接稳定性其图论模型的基础不变，这些方法都可以借鉴，笔者将用这些方法来对链接的稳定性进行打分，从而确定链接的稳定性。

在电信网络中一个现实情况是几家电信运营商并存，出于商业原因各运营商之间的数据并不共享，于是单一运营商并不能完整获知电信网络拓扑结构。如图1所示，运营商A只能获得自己网络的用户(以下称为本网用户)信息，而其他运营商的用户(以下称为外网用户)虽然与本网用户有联系，但其信息无法获得。这就给研究工作带来了巨大的挑战:不管是基于共同邻节点还是基于路径的方法，都不能直接应用于电信网络。例如，从图1可以看出，边a连接着本网用户x与外网用户y，运营商A无法获知y的度，也无法计算x与y的全路径。这并不意味着在现有信息条件下运营商不能对链接的稳定性做出判断。

2 权重和度对电信网路链接稳定性的影响

所采用的数据为某省会城市电信公司的5 000名CDMA用户4个月(2010年1月到4月)的通话清单，出于个人隐私和保密考虑，这些用户的个人信息和联系人信息已经匿名处理。为了使研究具有尽量客观的结论，5 000名CDMA用户为随机选取。1月和2月的数据作为训练数据，3月和4月的数据作为测试数据。

图1 电信网络联系人拓扑图

链接稳定性和链接预测最大的不同在于，链接稳定性研究的是已存在的链接，而链接预测则是预测现在还不存在的链接在将来是否会出现，在实际应用中这两个问题同等重要。

笔者统计了d(u)在2010年1月和2月的比值，并对该比值求对数，即:

其中，Ctcu为用户u的度变化系数(以下简称变化系数)，显然，如果两个月的度差异越小，则变化系数越接近0。这5 000个用户的变化系数分布情况如图2所示。

图2中曲线为高斯拟合曲线:

拟合的结果:a=0．04，b=0．005，c=0．14。

从实际图形和拟合结果都可以看出，链接减少和增多的情况大致相同，这也说明如果在已知全拓扑结构信息的前提下，链接预测和链接稳定性研究思路大致相同。

图2 电信用户链接变化情况

根据人们日常通话习惯的特点，有两点值得注意:一是某段时间内联系某个联系人的次数;二是某段时间内与多少个联系人联系过。在图论模型里，前者可以看成是某条链接的权重，联系某个联系人次数越多，这条链接的权重越高;后者可看作这个节点的度，不同联系人越多，这个节点的度越高。在限制条件下这里仅取链接两个节点中的一个节点进行度的测量。

在图论模型中，节点u、v代表两个用户，如果他们在时间［t0，t1］内有联系，则链接 e=(u，v)在子图 G［t0，t1］中存在，链接 e的权重 w 为 u、v的联系次数。u的度为u的邻居节点的个数，即用户的联系人个数，用d(u)表示。

(1)链接权重的影响。以边权重w为变量，P{w=k}表示当权重为k(k=1，2，…)时稳定性，即:

式中:E［t0，t1］、E［t2，t3］分别为子图 G［t0，t1］、G［t2，t3］的边集;Ew=k表示权重为 k 的边集;|*|为集合内元素的个数。

笔者统计了5 000个电信用户构成的电信网络的链接权重的稳定性，如图3所示。

图3 链接权重对链接稳定性的影响

可以看出随着链接权重w的增加，稳定性也增加，边权重和稳定性有正相关关系，可用指数函数f(k)=1 －e－λk来拟合 P{w=k}的概率，其中λ = －0．177，k为链接权重。

(2)节点度的影响。从上述的各种方法来看，节点u、v之间的链接稳定性与这两个节点的度有关系，但是由于实际条件仅能获知其中一个节点的度，故选择一条链接中任一个节点u，研究u的所有链接的平均稳定性与d(u)的关系，u的平均链接稳定性记为sta(u)，定义如下:

其中，Eu为含节点u的边集。统计的5 000个电信用户的d(u)和sta(u)的关系如图4所示。

图4 节点度对链接稳定性的影响

由于只测量了其中一个节点的度，因此稳定性的波动比较大，但仍然呈现一定的规律性。从图4可以看出，节点度在40以下时，随着度的增加平均稳定性也增加，度在40以上时，平均稳定性在0．39左右波动(0．39为全部链接的平均稳定性)。笔者用指数函数来拟合。

其中，a=0．177，μ = －0．058 9，d 为节点u 的度。综合图3和图4，可得一个电信用户链接稳定性计算模型:

其中，stae为链接e的稳定性打分;w0为调节因子，介于0到1之间;f(k)为边权重拟合函数;k为该链接的权重;f(d)为节点度拟合函数;d为已知的一个节点度。用该模型对链接进行打分，得分越高则稳定性越高。根据实际数据，f(k)的分辨度较f(d)要好，因此调节因子一般大于0．5。

3 结果评价

笔者将提出的模型与基于共同邻节点各种方法进行对比，对比的机制如下:按照某种方法对所有考察的边进行打分后，按照得分高低顺序进行排序，然后将得分平均分为若干段，计算每个分段的平均稳定性，得到一个序列。如果该方法具有较高的可信度，则该序列应该是单调下降的，且各相邻分段之间有足够的差异，差异越大越好。

这里将笔者提出的方法与所介绍的各种链接预测方法进行比较。将打分按照从高到低平均分为10段，调节因子w0取0．8。为了更直观地比较各方法的性能，给出了变化曲线，如图5所示。训练集的链接共有15 689，测试集的链接共有16 102，其中公有链接数为6 118，平均稳定性为0．39。在图5中，笔者提出的方法用粗线条绘出，平均稳定性用细实线绘出。

图5 各种链接方法的稳定性比较

从图5可以看出，笔者提出的方法性能最优，其曲线斜率最大，且没有得分低而稳定性高的情况(打分顺序颠倒)，在其他的方法中，共邻点的方法性能较好，索尔顿指数和索伦森指数性能较差。这是因为在电信网络中随着节点度的增加，链接稳定性是增加的，但是索尔顿指数和索伦森指数却认为节点度增加会导致稳定性降低，这两种方法不适用电信网络。另外，各种方法都存在顺序颠倒的情况。

4 结论

笔者对电信用户链接的稳定性进行了分析，得到一种能够准确评价电信用户链接稳定性的方法，将该方法与经典链接预测的方法进行对比，该方法具有较高的准确性，应用也很方便，不需要大规模的计算。分析结果可归纳为以下几点:

(1)两个不同时间段电信用户联系人数量增多和减少的概率基本相等，在不同月份之间的联系人数量比值求对数的概率分布可以用均值为0的高斯函数近似;

(2)电信网络链接稳定性和链接权重有正相关性，联系频度越高该联系人的稳定度越高，当联系频度超过6次时，稳定度大于0．7，当联系频度超过15次时，稳定度大于0．9，其关联性可用指数函数近似;

(3)链接稳定性和节点度有正相关性，但当节点度超过40，链接稳定性接近整体链接平均稳定性，其关联性可用指数函数近似;

(4)电信网络有其特殊性，即运营商仅能获知部分节点的拓扑信息，因此基于全路径集的链接预测方法不能直接应用到链接稳定性判断，笔者提出的方法具有较高的准确性和较佳的实用性。

笔者的结论对于电信用户的行为分析特别是联系人方面的行为分析具有重要意义，例如对于网络底层而言可以用于基于移动节点通信概率的网络资源分配和物理层协议设计，对于网络应用层有助于研究用户之间的社会关系，更好地进行客户关系管理等。

［1］ 中华人民共和国工业和信息化部．2010年3月统计数据［EB/OL］．［2010 －11 －01］．http://www．miit．gov．cn/．2010．3．

［2］ TAM W M，LAU F C M，TSE C K．Traffic analysis of a mobile cellular system based on a scale－free user network and a power－law－distributed mobility model［C］//IEEE Asia Pacific Conference on Circuits and Systems．［S．l．］:［s．n．］，2008:1120 － 1123．

［3］ GONZALEZ M，HIDALGO C A，BARABSI A L．Understanding individual human mobility patterns［J］．Nature，2008(453):779 －782．

［4］ SONG C，QU Z，BLUMM N，et al．Limits of predictability in human mobility［J］．Science，2010(327):1018－1021．

［5］ APOLLONI A，CHANNAKESHAVA K，DURBECK L，et al．Study of information diffusion over a realistic social network model［C］//International Conference on Computational Science and Engineering．［S．l．］:［s．n．］:2009:675 －682．

［6］ 张奇支，廖建新．移动智能网用户的通话时长模型分析［J］．高技术通讯，2006，16(4):1 －4．

［7］ GETOOR L，DIEHL C．Link mining:a survey［J］．Sigkdd Explorations，2005，7(2):3 －12．

［8］ LIBEN － NOWELL D，KLEINBERG J．The link prediction problem for social networks［C］//Proceedings of the 12th International Conference on Information and Knowledge Management．New York:ACM Press，2003:556－559．

［9］ TASKAR B，WONG M F，ABBEEL P，et al．Link prediction in relational data［C］//Proceedings of Neural Information Processing Systems．Cambridge:MIT Press，2004:659 －666．

［10］ HASAN M A，CHAOJI V，SALEM S，et al．Link prediction using supervised learning［C］//Proceedings of the Fourth Workshop on Link Analysis，Counterterrorism and Security，Philadelphia．PA:SIAM Press，2006:443－461．

［11］ POPESCUL A，UNGAR L H．Statistical relational learning for link prediction［C］//Proceedings of the Workshop on Learning Statistical Models from Relational Data at I JCAI．New York:ACM Press，2003:81 －90．

［12］ ADAMIC L A，ADAR E．Friends and neighbors on the Web［J］．Social Networks，2003，25(3):211 －230．

［13］ NEWMAN M E J．Clustering and preferential attachment in growing networks［J］．Physical Review E，2001，64(2):1 －4．