一种从移动通信数据中现发团体结构的方法

1《浙江工商大学学报（自然版）》排版格式样本一种从移动通信数据中发现团体结构的方法马力(浙江工商大学计算机与信息工程学院，杭州310035)摘要：本文提出了一种从移动通信数据中自动发现团体结构的方法。该方法采用改进的基于边的介数的聚类算法，可以从信息流图中快速确定团体结构。用一个时间跨度为2个月，容量为12251条记录的实际的移动通信数据集测试该方法，结果证明该方法能有效地确定团体结构。关键词：介数；复杂网络；移动通信；算法中图书分类号：文献标识码：文章编号：0引言研究社会网络中的团体结构，关于确定在线团体的研究越来越多。许多研究者把电子邮件列表和个人主页作为社会关系的在线代理，并且利用这些在线代理确定机构中的团体结构[1-2]。如Tyler等利用电子邮件列表作为人际交流的指示器，提出了一种确定一个机构中的团体结构的全自动的方法[3,9]。1网络团体结构的定义若论文受到省、部级以上基金项目支助，请注明基金名称和项目号实际的网络往往具有团体结构，其中一些节点相互之间的联系形成了一个紧密的团体，而这些团体之间却只有松散的联系，如图1所示[4]。图1具有3个团体的网络收稿日期：2005-10-21基金项目：国家自然科学基金（69674013）作者简介：马力(1966-)，男，浙江绍兴人，浙江工商大学计算机与信息工程学院副教授，主要从事复杂网络和数据挖掘研究。3到8个图序码用阿拉伯数字，图序与图题之间空一个字距章条序码用阿拉伯数字二十字以内100-300字若论文受到省、部级以上基金项目资助，请注明基金名称和项目号同一处引用多篇文献须将各篇参考文献的序号全部列出，各序号间用“，”。如序号是连续可标注起止序号，中间用“-”连接。2在数学上，网络一般表示成图),(EVG，其中集合V表示节点（对应于网络中的个体），集合E表示连接结点的边（对应于个体间的关系）。设Ai,j是G的邻接矩阵（AdjacencyMatrix），则对于G中的结点i，其度值（Degree）jjiAk。考虑一个子图GW，若Wi，则节点i的度值度值可以两个部分，一部分是节点i与属于W的节点相连的边数：jiWjiniAWk,)(；另一部分是节点i与V以外的节点相连的边数：jiWjoutiAWk,)(。若（1）成立，则称W是G中的一个团体，式中α越大则W的团体特性越明显。)()(WkWkoutiini，.1,Wi（1）2基于边的介数的网络分割算法从网络中发现团体结构可视为网络分割问题，传统的方法有谱分割法（SpectralBisection）和等级聚类法（HierarchialClustering）[5-6]。谱分割法将网络一分为二，当网络中团体数比较多时，往往不能给出一个好的结果。等级聚类法不能直接给出网络中团体数，而且对于大型网络并不适用。Given和Newman于2002年提出了基于边的介数的聚类算法（G-N算法），并将其应用于社会网络和生物网络的团体结构分析。[7]介数（Betweenness）是由Freeman于1979年首先提出的。在图),(EVG中，设σst=σts代表从节点s∈V到结点t∈V路径的数目。设σst（v）代表从节点s到结点t的最短路径经过节点v∈V的数目。则节点的介数的定义是：[8]VtvsststBvvC（2）我们同样可以定义边的介数。在图),(EVG中，设σst（e）代表从节点s到节点t的最短路径经过边e∈E的数目，边e的两个端点分别为u、v。则边的介数的定义是：EeVtvusststBeeC,（3）边的介数决定于通过它的最短路径数1。络中团体间的边连接了许多不同团体中的节点，所以其介数大，而团体内部的边的介数相对较小，这种特性可以用来区分团体间的边和团体内部的边。考察图2所示的网络，它含有1#和2#两个明显的团体，这两个团体有边AB相连，边AB具有最大的介数。如果去掉这条边，则网络分解为两个独立的团体。对于一个待分析的网络，我们计算其每条边的介数，确定其中介数最大的边，然后将它们删除，然后再计算剩下边的介数，再去掉介数最大的边。重复去边过程，直到所有边都被去掉，记录所有的去边过程，反过来就是各个结点组成团体的顺序，这就是基于边的介数的聚类法[9]55。1最短路经数是两节点之间的距离最小的路径数。公式编号左对齐线段斜体点用斜体一般集合符号斜体公式居中同一文献多次出现，要标注页码变量\变动附标用斜体解释性语言用脚注3图2连接不同团体的边具有大的介数3发现团体结构的方法我们对基于边的介数的聚类法进行了改进，以此为基础，设计了一种从移动通信数据中发现团体结构的方法，它主要由数据采集、数据处理、网络分割和结果验证四个步骤组成。3.1数据采集数据采集是发现团体结构的方法的基础。首先确定一个网络（如某个班级），然后确定数据采集的起始和终止时间，再要求该网络中的每个成员提供上述时间段内的移动电话通话清单。目前中国移动和中国联通两大移动通信公司都提供通话清单下载服务，下载的文件为TXT格式，所以如果网络中的成员积极配合，可以方便地采集数据。3.2数据处理数据处理将采集的原始数据转换为邻接矩阵。首先，本着保护个人隐私的原则，对原始数据进行了筛选，删除了收件人或发件人为网络以外人员的通讯记录，同时对每条记录的发送人（呼叫方号码）和接受人（接听方号码）进行加密。然后，为了定量分析网络中成员之间的联系，我们对不同的移动通信方式定义了具体的通信量分值，见表1。表1不同通信方式的通信量通信方式通信量1个短信11次持续时间小于3分种的通话21次持续时间为3-10分种的通话41次持续时间大于10分种的通话6这样，网络中两个成员i、j之间的关系可量化为其总的通信量ijF，即：321642cccsmsijnnnnF（4）式（4）中smsn是成员i、j间发送的短信个数，1cn、2cn和3cn分别表示成员i、j间的3分钟以内的通话次数、3-10分钟的通话次数和超过10分钟的通话次数。ijF越大，表示成员i、j的关系越紧密。假定网络中的成员数为n，则通信量的阈值HF为：章条层次一般不超过四级，各级之间加小圆点,末尾一级码不加小圆点表序与表题之间留一个字距，对整个表格左右居中4)1(/)(2%5min%5maxnnFFFFjiijijijH（5）式（5）中%5maxijC表示总通信量排在最前5%的成员对的总通信量之和，%5minijC表示总通信量排在最后5%的成员对的总通信量之和，用来控制阈值的大小，取05~0.6。3.3网络分割网络分割是发现团体结构的关键步骤。G-N算法的特点是反复去除介数最大的边，作为一种聚类算法，反复去边的过程一直到没有剩余的边才停止，这样最后并没有直接给出网络的团体结构，还需再作进一步的分析处理。可以看出。去除的边太少，不能划分出各个团体；去除的边太多，团体划分的过细，形成太多的孤立点和“两人世界”，与实际情况都不符合。所以我们必须确定一个去边过程能自动停止的条件，当该条件成立时，去边过程刚好将联系复杂的网络分割成若干个团体内部紧密联系的团体时。为此，我们引入一个阈值HB作为去边过程停止的信号。当网络中所有边的介数均小于阈值HB时，去边过程自动停止。meCBEeBH/))((（6）式（6）中m是网络中的边的数目，用来控制阈值的大小，取05~0.6。改进后的G-N算法如下：3.4结果验证为了验证方法的正确性，需要对于网络中的成员逐个进行采访，在采访中，我们首先向他们介绍了他们被归类于某个团体，然后请他们评论这些结果。采访的主要内容见表2。根据采访结果，就可以评价方法的正确性。表2采访内容问题回答你认为你属于被划分的团体吗？A、是B、不是你所在的团体是否多了某个人？A、是B、不是你所在的团体是否多了某个人？A、是B、不是请描述你所在的团体的意义和特点你对该算法的总体评价如何？100、90、80、70、60、50、40、40以下4实例按照发现团体结构的方法，我们开发了专用的软件系统，软件系统具有数据录入及管理、数据处理、网络分割和验证结果分析等功能，可以从移动通信数据中自动发现网络团体结构。我们用浙江工商大学某个班级的移动通信数据测试了我们的算法和软件系统。所采集的数据介于2003年12月到2004年1月之间，总共采集了12251条移动通讯记录。由引理得dxexxdxxexxyxdxxxxxx)1()(2222222323)2(222xexcxyx=正体正体5)2(2xexx5结束语我们的方法是基于无权网络的，即只将人际关系简化为“有关系”和“无关系”两种状态，这种处理方法丢失了不少有用的信息，今后准备研究采用加权网络，使从移动通信数据中生成的网络更加符合实际的网络。另外，我们希望扩大网络的规模，采集更多的信息，用来测试我们的方法。参考文献：[1]葛克昌.所得税与宪法[M].北京:北京大学出版社,2004:122.[2]千野忠勇．亚洲金融危机、资本账户开放与区域合作[C]//中国人民银行国际司．东盟与中日韩短期资本流动管理与资本账户开放高级研讨会论文集．北京：中国金融出版社,2003：13-16．[3]王斌．信息技术与信息服务[M]//许厚泽，赵其国．信息技术与应用．北京：中国社会科学出版社，1998：121-140.[4]国家标准局信息分类编码研究所．GB/T2659—1986世界各地和地区名称代码[S]//全国文献工作标准化技术委员会．文献工作国家标准汇编：3．北京：中国标准出版社,1985：90-99．[5]金子宏.日本税法[M].战宪斌，郑林根，译.北京:法律出版社,2004.[6]黄祖洽．软凝聚态物理研究进展[J]．北京师范大学学报：自然科学版，2005,41(1)：115-121．[7]丁文祥．数字革命与竞争国际化[N]．中国青年报，2000-11-20（15）．[8]张志祥．间断动力系统的随机扰动及其在守恒律方程中的应用[D]．北京：北京大学数学学院，1998．[9]姜锡洲．一种温热外敷制备方案：中国，88105607．3[P]．1989-07-26．[10]ALEXANDERN．Internationalretailing[M]．Oxford：Blackwellbusiness，1997：23-26．[11]ALEXANDERN，MYERSH.．EuropeanretailexpansioninSouthEastAsia[J].EuropeanBusinessReview,1999,34(2)：45-50．[12]杜莲．“9·11”事件影响英国出版[EB／OL]．（2001-09-29）[2006-01-27]．．[13]莫少强．数字式中文全文文献格式的设计与研究[J／OL]．情报学报，1999，18（4）：1-6[2001-07-08]．……．[14]奚纪荣，邱志方．武略文涛[M／OL]．上海：汉语大词典出版社，2001：13[2006-01-25]．……．数学式转行时最好在紧靠记号=，+，-，/等后断开连续出版物的析出文献学位论文专利文献最后这五项为电子文献格式，联机文献心备（更新或修改日期）[引用日期]．获取和访问路径．报纸英文人名用大写6[15]杨林江．沥青混凝土再生搅拌机：中国，CN200510049046．3[P／OL]2005-08-03[2006-04-07]．……．[16]王慧敏．塔里木又现百万吨级油田[N／OL]．人民日报，2004-01-05（2）[2006-01-27]．