金欣1,2 王晶1,2 沈奇威1,2

(1.北京邮电大学网络与交换技术国家重点实验室 北京100876)

(2.东信北邮信息技术有限公司 北京100191)

摘要：社会网络分析是数据挖掘的一个分支，而自中心网络是社会网络分析的一个重要组成部分。自中心网络能够通过研究个人与周围环境的交互以及环境的特征分析人本身的特征。近年来数据挖掘在电信领域的应用越来越广泛，而自中心网络从人与环境交互的角度为数据分析提出了新的思路，但是由于数据量、数据维度、计算复杂度等原因，传统的计算方式不能应付海量数据的自中心网络生成和分析的需求。本文首先给出了基于mapreduce模型的传统自中心网络生成算法的实现，然后提出了新的基于三角形提取自中心网络生成算法并给出了基于mapreduce编程模型的实现，该算法针对mapreduce模型和真实的社会网络进行了优化并实现性能提升。最后对两种算法进行运行时间和IO的比较。

关键字：社会网络分析 分布式 hadoop mapreduce数据挖掘 自中心网络

 

High Efficiency Implementation of a Distributed Egocentric Network Generating Algorithm

Jin Xin, Wang Jing, Shen Qi-wei

(State Key Laboratory of Networking and Switching Technology, Beijing University of Posts

and Telecommunications, Beijing 100876, China)

(EB Information Technology Co. Ltd., Beijing 100191, China)

Abstract:Social Network Analysis(SNA) is a branch of data mining, and egocentric network is an important part of SNA. Basing on the researching of the relation between personal and the culture he is in and the interactive between he and the other persons, we can find out a lot of character of the person by analysis of egocentric network. Recently, data mining is more and more widely used in the telecommunication area, and egocentric is a new idea that trade the person as a part of the whole network. But because of the size of data, dimensionality of data and the complication of the computation, traditional methods is not suitable for this kind of application. In this article, we give the implementation of the tranditional egocentric algorithm based on mapreduce module . And then we propose a new egocentric network generating algorithm based on the discovery of triangles. After that, we give the implementation of the new algorithm based on the mapreduce module. In this new algorithm, we make some optimize in connection with the mapreduce module and the character of the real social network to enhance the efficiency. At last, we will compare these two algorithms by time consumed and IO.

Key words: SNA; distribute; hadoop;mapreduce;data mining;egocentric network

 

1、概述

 

      随着社会的发展和技术的进步，人与人之间的联系越来越紧密，手机正是一种为了满足人们互相沟通的需求而出现的工具。据工信部今年二月份公布的数据，中国的手机用户已经达到了7.74亿[1]，而在这个庞大的数字之后，慢慢浮现出来的是更加丰富的用户需求，用户不仅仅满足于打电话、发短信，各种数据业务正在飞速走进我们的生活，如手机阅读、多媒体业务、移动广告等等。

      随着数据业务的不断丰富和电信运营商之间的竞争愈发激烈，提供更好的服务，提高用户体验成为降低用户流失、保证市场份额的关键。然而如何提供更好的服务呢？通过对用户数据的分析了解用户喜好，并向用户提供个性化的信息服务是最主要的方式之一。通过数据挖掘的方式，电信运营商可以了解用户的个人喜好、消费倾向等等，利用这些信息，在提高服务质量的同时努力实现精准的广告投放增加收益。如何高效的对数以亿计的手机用户的个人数据、业务数据、通话数据等等进行处理，成为运营商面临的新挑战。

      社会网络分析是数据挖掘的一个分支，它通过对人与人之间的关联进行分析来寻找有价值的信息。自中心网络是指以个人为中心的社会网络分析，通过分析个人与周围环境的交互来挖掘个人特征。手机本身就是人们之间沟通的工具，运用社会网络分析的方法对手机用户的通话网络、短信网络等进行分析是利用数据挖掘寻找用户特征的重要手段。

本文将逐步设计基于hadoop分布式计算平台的自中心网络生成算法实现。该算法针对mapreduce的分布式计算模型，从数据分布、IO等方面对算法进行改进，最终给出一种适合mapreduce的高效的自中心网络生成算法。

下面的论文主要内容包括：第2节介绍社会网络分析和自中心网络及其在移动领域中应用的困难；第3节给出传统自中心网络算法的mapreduce实现；第4节介绍基于三角形寻找的自中心网络算法设计和实现；第5节对不同实现进行IO和运行时间上的 比较；第六章对论文进行总结。

 

2、社会网络分析和自中心网络

 

      传统的机器学习和数据挖掘任务处理的对象是单独的数据实例，这些数据实例往往可以用一个包含多个属性值的向量来表示，同时这些数据实例之间假设是统计上独立的。而社会网络分析以人为个体，通过分析人与人之间的关联寻找网络和个人特征。社会网络分析分为两个部分，一是对网络整体进行分析，例如分群、网络演变等的研究，二是自中心网络，就是以个人为中心通过分析它与周围环境的交互来分析其特征。由于自中心网络的分析可以挖掘出个人的特征，相比整体网络分析更加适合个人喜好、消费倾向、骚扰电话分析等信息的挖掘。

      相比facebook等构建的社会网络而言，手机用户构建的网络更加生活化和真实，因此对社会网络分析具有更大的价值。随着手机用户的不断增多和移动业务的不断丰富，人与人之间的交互越来越复杂，用户交互数据无论从维度上还是从数量上都对移动运营商的数据分析工作提出了挑战。而近年来分布式计算技术的高速发展为这种海量数据分析的应用提出了新的解决方案，并且随着分布式计算技术的愈发成熟，其在移动领域的应用也越来越多[2]。通过将用户数据分布在各个节点上进行分布计算可以显著提高运算速度，特别是对于自中心网络来说，由于是以每个用户为中心来分析数据，因此更加适合通过分布式的方式进行计算。

      但是由于社会网络分析是通过数据之间的关联进行分析，所以用户与用户之间的数据传递会使得系统的IO消耗十分严重，这是研究分布式社会网络分析算法必须要解决的问题。

 

3、基于mapreduce的传统自中心网络生成算法

 

      mapreduce是一种计算模型，每个mapreduce分为一个map过程和一个reduce过程，map和reduce的输入输出数据都是采用键值对的方式进行描述，map会对每一个键值对进行处理，处理结果用键值对的形式进行输出，输出的结果相同key值的会汇总到一起由reduce进行处理。详细的mapreduce编程模型介绍可以参照文献[3]。

      算法的存储模型采用以点为基础存储整个社会网络图。每个点被分配一个id，用一个对象表示。这个对象除了存储点的id之外，还有与该点所有相连的边。对象表示的点本身为中心点，边用除了中心点之外的另外一个点来表示。这个样子所有的点对象就可以构成一个完整的社会网络图。

      一个点的自中心网络由两部分组成，一是所有和自己相连的点，二是这些点之间的边。任何一个自中心网络算法都要首先找出每个点所在的自中心网络。在现有的存储模型中对于一个点对象来说，已经存储了自己中心网络中的点以及和自己相连的边，因此自中心网络生成工作的核心就是找到这个点的邻居之间的边。传统的自中心网络生成算法就是遍历自己所有邻居的邻居来找到自己邻居之间相连的边，下面给出传统自中心网络算法的分布式实现。

      整个算法由一次mapreduce过程就可以完成。在map中对所有点依次进行处理。每个点的处理过程如下：

      1)遍历该点的所有邻居，以邻居的id为键，以点对象本身为值输出记录。

      2)以自身点id为键，对象本身为值输出数据。

      经过map过程，reduce接收到的每个键值对应的就是中心点和他的所有邻居，邻居对象包含了这个邻居的边信息。通过将邻居对象和中心点对象的边进行比较就可以找到该邻居与中心点其他邻居之间是否有边存在。最终我们可以找到所有相连的邻居，从而形成该点的自中心网络。

 

 

图1 自中心网络生成算法实例图

     

      假设图1是一个社会网络图的子图，A至F是其中的6个点，设A至F代表的是点对象，而a至f是点的id，则在map中，A会输出5条键值对分别为a‐>A、c‐>A、d‐>A、e‐>A、f‐>A；在reduce中，a对应的数组中包含的是(A,C,D,E,F)，通过对这些对象的边信息的遍历，可以找到三条边，结合A对象中的信息，生成以A为中心点的自中心网络。

      由于在reduce中相同键值下的数据排序不能确定，所以不能知道哪一个是中心点，所以不得不将所有数组中的数据先存储在内存中，然后通过将每个对象的id和key进行比较，相等的就是中心点。这种方式在一个点的邻居很多的情况下会导致内存消耗非常严重。这个问题可以用mapreduce中常用的技巧secondary sort[4]来解决，这里就不详述了。

 

4、基于寻找三角形的分布式自中心网络生成算法设计与实现

 

      第三节描述的算法是自中心网络生成算法基于mapreduce的一个直接而简单的实现，该算法有三个明显的不足。

      1、mapreudce程序的主要瓶颈在IO，而社会网络分析算法的IO消耗也是非常严重的。但是在这个算法中传输了许多不必要的信息，比如点C以a为键输出的数据是为了生成以A为中心的自中心网络，由于传送的是对象，所有该点的邻居信息，包括B都在对象中，但实际上是不需要的，但是由于其不了解A的情况所以不能判断哪些边是冗余的。在一个庞大的网络中，这种不必要的数据将是非常巨大的，因此大大影响了系统的IO负载，降低了算法的性能。

      2、分布式算法的效率和数据的分布有很大关系。根据文献[5]分析，在一个真实的网络中，往往有很少的一些点，这些点的度数非常的大，在一个庞大的社会网络图中点的度数分布式呈指数分布的。而第三节描述的算法由于以中心点为计算的核心，必然会因为一些度数很大的点使得某些点的计算量非常大，从而影响整个程序的执行效率。

      3、一个点如果有很多的邻居，为了找到所有相连的边，对每一个邻居的边都要进行一次完整的遍历。在这个遍历过程中有很多是不必要的。

      可以看出这些缺陷都是由于算法实现采用的基于中心点遍历邻居的方式导致的。这种方式由于图中点的差异必然导致数据分布的不均衡，而由于在每个点的处理过程中的重复且复杂的计算，使得单点负载严重影响性能。

      因此需要换一种思路，才能解决上述的几个问题。一个点的邻居如果相连，那么着两个相连的邻居和中心点就可以构成一个三角形。那么如果找到与一个点相关的所有三角形，就相当于找到了所有属于该点自中心网络的边。通过文献[6]的介绍可以看出，找三角形这种操作实际上是将一个大的图打散成为许多很小的部分，非常适合分布式计算。

      基于以上分析，我们提出了一种新的生成自中心网络的算法，该算法首先找出图中的所有三角形，在找出所有三角形以后，只要计算每个点存在于哪些三角形中，就可以判断该点有哪些邻居之间是相连的。

      改进后的算法需要两个mapreduce过程，第一个mapreduce过程找出所有三角形，第二个通过三角形得到自中心网络。

第一个mapreduce过程中，在map中输出一个点邻居的所有邻居对，以中心点和两个邻居用分隔符相连作为键，值为空。reduce中每个键对应的相当于是一个三个点组合。如果一个三角形存在，则这个组合会收到三条记录。通过简单的计数可以判断这三个点在图中是否可以组成三角形。如果可以，则将该记录分别以三个点为键值输出三条记录。例如图1，A点需要输出6条记录，每条记录是一个字符串，而采用原算法需要输出四条记录，每条记录都是保存该点所有的边信息的点对象。而且由于新思路没有以点为中心来计算，所有的数据会更加均匀的分布在各个节点上从而保证了负载的均衡，解决了单点负载问题。实际上这个过程可以优化，如果三个点构不成三角形，那么肯定只能接收到一条记录。这个样子利用id排序我们为每个三角形只输出两条记录，相当于节省了三分之一的IO。通过这一步mapreduce过程，可以得到和三个三角形。

      第二个mapreduce过程中，将原图和第一个mapreduce运算的结果同时作为输入进行一次计算，在reduce中一个点可以接收到许多的三角形，每个三角形对应一条边，将这些边

      汇总起来就可以形成该点的自中心网络。这个过程也有单点的问题，但是由于运算过程仅仅是简单存储，所以负载问题并不严重。

 

5、算法比较

 

      为了比较两种算法的性能，对算法进行了测试比较。测试数据是某论坛数据，通过回帖信息建立起一个社会网络。用户数量为78790，为了使得输入会分布在不同的机器上，我们将其按大小均匀分为六个文件，相应的我们使用三台性能相同的机器搭建了一个hadoop集群，每台机器可以同时执行两个map任务和两个reduce任务。

      使用原算法总共运行时间为1分57秒，而找三角形方式两步过程的运行时间总共为44秒。效率提升主要在三方面，一是map到reduce的IO原算法为794兆，新算法两步总共为296兆，IO消耗降低很明显。二是原算法不同reduce之间运行时间最短为1分18秒，最长为1分42秒，运行时间最长的机器使得整个算法运行时间延长了24秒；而新算法中不同reduce运行时间相差不超过2秒。三是由于算法的不同，每个reduce运行时间都少了很多。

      虽然这个数据量不是很大，但是可以明显看出新的实现方式对算法性能的影响。如果数据量进一步增大，那么由于IO和负载平衡的原因，新算法的优势将会更加明显。这个算法的优势在于利用了社会网络的整体稀疏和度数指数分布的特点改进了算法的IO和负载平衡，从而提高算法性能，但是如果图的密度很大，且所有点度数都很大，新算法的优势就不存在了，而且由于多了一个mapreduce过程，整个算法性能可能还低于原算法，但是根据文献[5]中的验证和分析，几乎所有的真实网络都是属于前一种的。

 

6、总结

 

      本文针对真实的社会网络特征和mapreduce分布式计算模型，提出了一种基于三角形查找的分布式自中心网络生成算法，用于解决海量数据自中心网络生成问题。该算法在处理真实的社会网络过程中，很好的利用了真实网络的分布特征，通过对IO和负载均衡的优化大幅提高了算法性能。但是如果整个网络是高密度且度数均匀分布的话，算法性能会低于直接的网络生成算法。但是对于手机用户构建的真实的社会网络的分析问题而言，该算法的优势还是比较明显的。

 

参考文献

[1] http://www.enicn.com/article/2010-02-04/0204610402010.shtml.

[2] 杨戈，廖建新，朱晓民，樊秀梅.流媒体分发系统关键技术综述[J]，电子学报，2009(1)，137-141.

[3] Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplied Data Processing on Large Clusters. In Proceedings of the 6th Symposiumon Operating System Design and Implementation(OSDI04), UsenixAssoc.,pages137C150,2004

[4]J. Venner. Pro Hadoop. Apress, Berkely, CA, USA, 2009

[5]R. Albert and A.-L. Barabasi, Statistical mechanics of complex networks, Rev. Mod. Phys. 74(2002),10-97.

[6]Graph twiddling in a mapreduce world. Computing in Science and Engineering, 11(4):29–41, 2009.

 

___________________________________

∗基金项目：国家杰出青年科学基金（No. 60525110）；国家973计划项目（No. 2007CB307100，2007C国家自然科学基金（No. 61072057，60902051）；中央高校基本科研业务费专项资金（BUPT2009RC050电子信息产业发展基金项目（基于3G的移动业务应用系统）