基于Hadoop的电信频繁交往圈算法研究

摘要：通过研究电信社交网络的个人交往圈和客户群，结合有向图和无向图，采用邻接链表，挖掘极大团，提出基于Ma⁃pReduce的频繁交往圈算法F-Graph，不仅找到频繁交往圈和客户群中的核心用户，同时减小了算法复杂度。利于运营商做出更科学的决策，提高市场竞争力。关键词：Hadoop；MapReduce；数据挖掘；极大团中图分类号：TP301文献标识码：A文章编号：1009-3044(2013)28-6380-05ResearchofAlgorithmsaboutFrequencyTelecomSNABasedonHadoopYANGMiao-miao,LIYue-hui,LIUJing,XUJing(CollegeofTelecommunicationandInformationEngineering,NJUPT,Nanjing210003,China)Abstract:Inthispaper,anewalgorithmcalledF-GraphwillbeproposedtostudythetelecomSNA.Combiningthedirectedgraphsandtheundirectedgraphstofindthemaximalcliquestofindthecorecustomersofclustersandtoreducethecomplexityofthealgorithms.Buythewayitwillbenefittheoperatorstomakemoreinformeddecisionstoimprovemarketcompetitiveness.Keywords:Hadoop;MapReduce;DataMining;MaximalCliques国内电信企业的数据电子化程度越来越高[1]，在竞争越来越激烈的市场环境下，电信企业迫切地需要一种高效的方式、精确的存取、及时的和可信的信息，提高市场的快速反应能力，并提高市场经营的服务水平。如今，运营商的数据积累已十分庞大，面对海量数据，如何快速存储和分析，对数据仓库已成为新的挑战。幸运的是，Hadoop-Apache软件基金会旗下的一个开源分布式云计算平台应运而生，可大大提升电信企业处理数据的能力。

以HDFS和MapReduce为核心的Hadoop，具有高容错性，高扩展性，高效性和高可靠性等优点[2]。用户可在低廉的计算机上部署集群，形成分布式系统，MapReduce能够高效地在分布式系统中并行地处理任务。因此，Hadoop在互联网领域中的应用越来越广。

图挖掘是挖掘交往圈经典算法，通常研究的图为简单的无向图，忽视了两个节点之间的许多信息。对于电信的语音清单，通话是有向的，只有有向图才能更好的反应两个通话者之间的通话频率，以及交往圈中的核心用户等具体的信息。所以改进已有的图挖掘算法，结合有向图和无向图模型才能快速挖掘出更准确电信交往圈信息。

第二部分为相关概念的描述，第三部分为算法的研究与分析，第四部分为实验及相关结果的分析，第五部分为结论。

1相关概念与描述1.1Hadoop-MapReduce框架MapReduce是一个海量数据集（大于1TB）分布式并行计算模型。Map函数用来接收一个输入key/value对，然后生成一批中间的key/value对，Reduce函数接收key和相关的value集合，并有相同key的value合并起来，输出键值对作为最终的结果。基于上述原理，Hadoop上的并行应用程序开发是基于MapReduce编程框架的，从而使的简化了程序，并实现了在计算机集群组成的云平台上，进行数据的高效存储和管理。1.2电信网络近年来，研究者越来越关注电信数据。Nanavita、Dasgupta和Hidalgo等人纷纷提出相应的模型，在电信数据研究方面做出巨大的贡献。大量的实验研究表明，复杂网络中节点的度值相对于它的概率满足幂率关系[3]，真实网络几乎都具有小世界效应[3]，人们更喜欢和自己具有相同特征（相似年龄，性别，爱好和地域）的人进行通信，而且与这些人更容易组成客户群，形成交往圈。1.3数据挖掘通过分析客户资料信息、语音清单和短息清单，发掘客户交往圈信息，帮助市场部门细分客户群，制定有竞争力和针对性的营

收稿日期：2013-07-22作者简介：杨苗苗，女，硕士研究生。6380

人工智能及识别技术本栏目责任编辑：唐一东

第9卷第28期(2013年10月)

ComputerKnowledgeandTechnology电脑知识与技术

销方案。为了得到更全面的交往信息，通过交往指数，综合衡量客户交往频繁度。主要通过以下两种方式挖掘客户交往圈信息：

1)分析以个人为中心的交往圈，从而提供客户交往圈展现，得到用户交往情况。将客户的交往圈按照呼叫时间分为生活圈，工作圈和综合圈，汇总不同圈中语音清单的总通话次数、通话频率=总通话次数/天数、通话得分=1-0.1×名次（通话次数倒序排列）、通话时长和通话时长得分=1-0.1×名次（通话时长倒序排列），短信清单的短信总数和短信得分=1-0.1×名次（短信次数倒序排列），最后计算出客户不同圈中的交往指数。经过调查，我们给出不同交往指数的计数公式如下：

生活圈交往指数=0.4×生活圈通话频率+0.2×生活圈通话得分+0.2×生活圈通话时长得分+0.1×生活圈短信得分+0.1×0(彩信指标为0)

工作圈交往指数=0.6×工作圈通话频率+0.1×工作圈通话得分+0.3×工作圈通话时长得分

综合圈交往指数=0.4×通话频率+0.2×通话得分+0.2×通话时长得分+0.1×短信得分+0.1×0(彩信指标为0)个人的交往圈中不同区域分布稠密程度，有助于看出客户的频繁交往圈，找到最有价值的客户，帮助运营商将更多注意力投向潜在的的优质客户。本部分借助有向图通过MapReduce汇总及可得到结果，我们可以得到个人交往圈分布图如图1，比较简单。由于社会网络的整体分布稀疏[4]，个人交往圈以每个用户为中心来分析数据，因此通过分布式的方式进行计算可以显著提高运算速度。

图1个人交往圈分布图2)通过分析语音清单，分析以客户为中心的交往圈，从而提供客户群交往圈展现，得到客户群交往情况，如图2(图2分别为客户群为3、4、5的频繁交往圈)。客户群为3的频繁交往圈包含着客户群为4、5的频繁交往圈信息，包含较多的重复信息，因此有必要挖掘最大频繁交往圈，通过F-Graph算法，来寻找电信社交网络的最大频繁交往圈。频繁交往圈中的核心用户广播消息范围广，影响力强，不仅对新产品具有最大的推广能力，而且对产品体验的结果可能影响其所在的整个交往圈，是运营商重点关注的对象。这里我们借助交往指数来分析交往圈中客户交往频繁度，从而找到客户群中的核心客户。也可借助关联规则研究交往圈中客户基本信息和使用产品，行为习惯等，帮助市场部门针对不同的客户群定不同的营销方案和做出科学的决策。这部分采用图算法[5]完成，是研究的重点和难点。

图2客户群交往圈分布图2最大频繁交往圈算法F-Graph2.1有向图理论图是研究社交网络的一种重要算法。通常可使用符号表示成G=(V,E)，其中V为节点集合，E为关系（边）的集合。无向图中，边记为（1,2），包含<1，2>和<2，1>两条边。有向图中，<1,2>表示从顶点1出发到顶点2的一条边。每个节节点的度TD(v)=OD(v)+ID(v)。

3流程/MapReduce编程通常研究交往圈采用图算法[5]，给定语音清单，一次通话的建立，即可用图的的一条边表示，通话者为节点，每个通话者呼入和

本栏目责任编辑：唐一东

人工智能及识别技术

6381

ComputerKnowledgeandTechnology电脑知识与技术第9卷第28期(2013年10月)

呼出次数总和即可用节点的度表示。传统分析交往圈的方法大都是分析简单的无向图，只关注两者直接是否有联系，忽略了交往的频繁度。也有研究交往圈采用有向图，时间和空间复杂度都很大，不利于企业进行快速交往圈挖掘。经过研究，提出频繁交往圈图算法F—Graph，结合有向图和无向图，利用MapReduce对数据进行处理，并将无向图转化成邻接链表[5,6,7]的形式。该算法包括三部分，有向图分析，图转化和图挖掘。3.1有向图分析首先对语音清单进行初步转化和汇总。每次通话的建立可以用有向图的一条边表示，这里我们定义每个节点的度表示该客户呼入和呼出次数总和，可以得出该客户正向呼叫次数占比=呼入/(呼入+呼出），对电信交往圈具有很重要的参考价值，也是下面

9,10]

剪枝的重要依据。考虑图挖掘算法中，无向图更利于挖掘极大团[8，。结合上述优点，首先统计每个节点的度，然后将有向图转化成无向图，并去掉重复边。建立一个新文件，存放无向图和每个节点的度，详细说明如下表1所示。

表1有向图的MapReduceMap1Reduce1Map2Reduce2

3.2图转化输入：语音清单；Key：边的每个节点；Value：每条边；

将每条边分解成两条，这两条记录的Key分别为一条边的边上的两个节点输入key：边的节点k1；value：list和Γ(k1)；统计每个节点的度

输出：有向图文件，k2为以k1为首节点的边，v2为有向边和k1的度。输入：有向图文件；Key：为以k1为首节点的边；Value：为有向边和k1的度。Identity输入key：边（Vi，V）value：节点的度j；IfVi输出：无向图文件，k3为边，v3为边两个节点的度通过统计，不管是按日还是按月，用户呼叫行为服从重尾分布。这里，研究的是交往频繁的核心用户和客户群，剪掉通话次数

小于等于1次节点，只考虑上面无向图文件中节点的度大于1的记录，可以大大提高数据挖掘效率。利用MapReduce（表2）对无向图文件进行处理，将其转化成邻接链表的形式。

表2图转化的MapReduceMapReduce

3.3图挖掘输入中key：边的头节点；value：边的尾节点；收集所有头节点相同的中间结果

输出：邻接链表中key：节点k2；value：Γ’(v2)，其中Γ(v2)={v2|v2∈Γ(v2)}；输入：无向图文件；中Key：行偏移量；Value：为每行记录内容；如果节点的度大于等于2，则作为中间结果存储输出中Key：边的头节点；Value：边的尾节点挖掘客户群频繁交往圈[8]，但首先需要知道节点v及其邻居Γ(v)。上述输出的图的邻接链表只包含图的一跳（one-leap）信息。

[7]

为了满足MapReduce分布式编程的思想，我们借助两跳（two-leap）信息，找到邻居的邻居Γ(Γ(v))，从而将两跳信息分布到同一个计算节点上。如给定一条记录<1;<2;3;4>>，表示其节点1和其邻居<.2;3;4>，将其形式转化（<2;<1;<3;4>>>，<3;<1;<2;4>>>和<4;<1;<2;4>>>）之后，被分解成若干个子图，然后进行分布式的极大团挖掘。构造一颗以4为顶点的子树，通过广度优先搜索，即可获得以4

[9,11]

为顶点的极大团(1;2;3;4)。为了挖掘联系更紧密，交往更频繁的客户群，这里采用顶点优先策略挖掘极大团，见表3。

表3图挖掘的MapReduceMap

输入：邻接链表；中Value：；

如果节点包含在Γ’(k1)，则输出>，否则输出输入中key：边的头节点；value：list；

-21474838以k2为根构造子树T

-21474838对树T进行广度优先搜索，i层搜索到的节点记vij，在每层裁剪掉以vij（vij>k2）为根的所有子树，并裁剪掉以vij(vij∉Γ’(vi-1)，即上一层没有此节点)为根的所

有子树

-21474838按节点序号的升序输出以k2为根的层数最多的子树及为所求极大团

输出：以v为顶点的极大团；

Reduce

通过两跳信息转化和剪枝，输出的极大团都是以最大顶点为开始的，保证了输出结果没有重复数据，同时也减少了运行和I/O6382

人工智能及识别技术

本栏目责任编辑：唐一东

第9卷第28期(2013年10月)

ComputerKnowledgeandTechnology电脑知识与技术

时间，提高了算法的效率。F-Graph算法的复杂度主要集中在图挖掘步骤，本算法是基于Hadoop平台，采用分而治之的思想，每部分使用的策略是相同的，然后再合并，所以极大团算法的复杂度为O(3c/3/m)，其中M为reducer个数，空间复杂度为网络中，又社交网络中度分布具有幂率特性[3]，则

(1)。

，复杂

表示c极大团的数目。计算所有极大团的空间复杂度为公式

(1)

4实验及其结果分析4.1实验环境实验环境和数据由某运营商的数据仓库提高。一个月的语音清单与短信清单已超过TB。数据先从ODS抽取到数据仓库，再

在云平台上通过Hive进行数据格式转化和脏数据清理等，数据量被整理成约2亿条，大大数据挖掘效率。文件的格式为Textfile格式。Hadoop环境中的配置文件没有修改，如备份数，默认为3[2]。由于Map数为轻量级，我们采用默认值。Reduce数主要与节点数有关，这里取Nnode×λ，其中λ为1.7到2之间。4.2集群环境信息表4Hadoop集群环境信息参数操作系统硬件配置

实际值

RedHatEnterpriseLinuxServerrelease6.3

(Santiago)（8CPU/48GB内存/20TB）

Namenode0:132.228.167.198Datanode:132.228.167.208Datanode:132.228.167.210Datanode:132.228.167.213Namenode:

132.228.167.216(备份服务器)

主机名称

4.3介质信息4.4结果分析本实验环境的介质信息如下：JDK：JRE1.7Hadoop(HDFS)：hadoop-1.0.3.tar.gzMysql：mysql-5.5.27.tar.gzMysql-jdbc驱：mysql-connector-java-5.1.22.tar.gz

为了测试算法的性能，加载不同的数据量，经过测试，得到算法运行时间，如图3。算法中每步所以时间与所用时间并不是成正比，随着数据量的增加，所用时间在缓慢增加。这是由于MapReduce的分布式运算在处理大数据时具有极大优势。

图3F-Graph运行时间F-Graph分三步，总时间还是随着数据量的增加而增加，显而易见，算法进行数据挖掘的时间短，效率高，因此此算法可靠且负载均衡。

本栏目责任编辑：唐一东

人工智能及识别技术

6383

ComputerKnowledgeandTechnology电脑知识与技术第9卷第28期(2013年10月)

经过试验，由图4中结果我们不难发现，随着节点数的增加，极大团也在增加。节点数相同时，边数越多，构成的团越多。人的通话行为服从重尾分布，所以边数并没有随着节点数的增加而快速增加。通常人的交往圈子比较固定，且具有小世界特点，所以随着极大团的增加，节点数为3的团在快速增加，这是因为社交网络的小世界性，节点数为4、5的团则缓慢增加。从结果可看成，本算法是可行的。

图4F-Graph挖掘结果社交网络具有小世界性，可以反映网络的局部特征，运营商的可以通过分析获得每个客户群中成员的年龄，性别，职业，级别，爱好和兴趣等等相关特征，对于推广新业务，减少客户流失，防止诈骗等有重要作用。将极大团文件和以个人为中心的交往圈文件进行关联，则可用客户的综合交往指数，工作交往指数，生活交往指数，前向通话量占比，前向时长占比和前向短信占比来描述此极大团的交往情况，从而得到频繁客户群的核心用户。

5结束语满足了电信运营商通过数据挖掘满足业务需求，提出一种基于云计算平台的挖掘电信社交网络的F-Graph算法，该算法分三大步：有向图分析，图转化和图挖掘。通过实验测试，证明了此算法具有可行性。研究的主要贡献是将无向图和有向图结合考虑，采用MapReduce算法得到极大团，不仅得到电信社交网络中个人交往圈的分布情况，也得到了核心客户群和核心客户的分布情况。有助于运营商在管理和决策方面的改进，在激烈的竞争环境中获得最大利益。

参考文献：[1][2][3][4][5][6]段云峰,吴唯宁,李剑威,等.数据仓库及其在电信领域中的应用[M].电子工业出版社,2003.Hadoop,http://hadoop.apache.org/.张光卫,康建初,夏传良,等.复杂网络集团特征研究综述[M].计算机科,2006,22(10).R.AlbertandA.-L.Barabasi,Statisticalmechanicsofcomplexnetworks,Rev.Mod.Phys.2002,74:10-97.Cohen,J.GraphTwiddlinginaMapReduceWorld.ComputinginScienceandEngineering2009,11(4):29-41.YuxiaoDong,QingKe,YananCaietalTeleData:DataMining,SocialNetworkAnalysisandStatisticsAnalysisSystemBasedonCloudComputinginTelecommunicationIndustry[M],CloudDB‘11ProceedingsofthethirdinternationalworkshoponClouddatamanagement,2011.41-48.[7]白云龙.基于Hadoop的数据挖掘算法研究与实现[D].北京邮电大学,2011.[8]JonathanCohen.Trusses:CohesiveSubgraphsforSocialNetworkAnalysis[J].NationalSecurityAgencyTechnicalReport,2008.[9]BrianAlspach,HeatherGavlas,MatejaSajna,etal.CycledecompositionsIV:completedirectedgraphsandfixedlengthdirectedcy⁃cles[M],JournalofCombinatorialTheory,SeriesA2003,103:165-208.[10]E.Tomita,A.Tanaka,andH.Takahashi.Theworst-casetimecomplexityforgeneratingallmaximalcliquesandcomputationalex⁃periments.TheoreticalComputerScience.363(1):28-42.2006.[11]FengZhao,andAnthonyK.H.Tung.LargeScaleCohesiveSubgraphsDiscoveryforSocialNetworkVisualAnalysis[C]//Proceedingofthe39thinternationalconferenceonVeryLargeDataBases.VLDBEndowment,2012;85-96.6384

人工智能及识别技术本栏目责任编辑：唐一东