社会网络社区识别方法研究

杨高明，李敬兆，张顺香，周华平

(安徽理工大学 计算机科学与工程学院, 安徽 淮南 232001)

0 引言

目前存在着各种各样的网络，诸如：社会网络、通讯网络、WWW、Internet、WSN、经济网络、神经网络、交通网络、电力网络等。这些网络看起来虽然千差万别，但实际上有着许多相似的性质，如聚类效应、小世界效应、以及结点度分布为幂律分布和某些结点间的异配性等。由于聚类效应的存在，社会网络中往往存在着一些联系紧密的结点构成的簇，所谓的社区识别指的是将这样的簇找出来以供进一步的分析和研究。无论是在社会网络还是其他类型的复杂网络的实际应用中，社区识别都是不可或缺的一个重要步骤。例如，针对犯罪和恐怖主义活动，美国执法机构利用相关部门提供的数据构建了庞大的信息网络，而且开发了对该网络进行知识发现和分析的工具CrimeNet Explorer[1]。为预测和找到各犯罪团伙和恐怖组织的首要和骨干分子，CrimeNet Explorer首先就要对当前信息网络进行社区识别以区分不同的犯罪团伙和恐怖组织，然后才能运用社会网络分析(Social Network Analysis，SNA)等方法和技术在所得到的各个社区中进行分析和确认[2]。社区识别方法的研究已越来越受到学术界的重视，但仍然存在一些缺陷和不足，主要表现为：针对的网络一般为同质网络，识别算法不是增量算法，需要先验或专家知识，沉淀在网络中的知识未能得到合理地利用，针对的网络往往是单关系网络，识别结果难以理解等。这些问题都需要学者进一步的研究。

1 社会网络概述

社会网络就是社会行动者之间连接而成的关系结构。人、班级、学校、公司、国家等都可认为是社会行动者，这些社会行动者之间可以存在各种各样的关系。社会网络分析(SNA)是由研究者利用实证数据构造的互动结构图，用以分析网络参与者之间的关系形态的技术。SNA的发展在西方已有了七八十年的历史，人类学、心理学、社会学、图论、概率论和统计学等多种学科和学派为其注入了强大的活力。但其作为一个明确的专门领域或研究方法的形成以及得到广泛的应用和发展，只是近一二十年的事情。利用SNA方法及其理论提供的一些科学概念和量度，如密度、点度中心性、绝对点度中心度、中间中心性、绝对中间中心度、相对中间中心度、接近中心度、绝对接近中心度等，能够对各种社会关系进行精确的量化表征和分析，从而揭示其结构，并对其产生的各种现象进行更加深刻而具体的解释。由于许多现象都可以用社会网络加以描述，所以SNA已经成为当前学术界一个非常活跃的研究课题。

国外对SNA的研究和应用已涵盖了诸多方面和领域，如犯罪网络、反恐网络、电子商务、疫情监测、作者合作网络、蛋白质相互作用网络、基因常规网络、邮件网络、虚拟学习、作者—主题分析、社区发现、空间文本挖掘、标签系统、虚拟社区、口语处理、角色识别、博客世界、青少年关系网络、社会层次发现、电话通讯网络、推荐系统、大型程序中Bug的预测和发现等。以上的这些列举，只是国外开展SNA研究的冰山一角，这些研究的总体脉络是：理论，实践，再理论，再实践，已形成了一个持续发展的良性循环。

相比较而言，国内对SNA的研究起步较晚。在改革开放之后，我国的SNA研究只限于社会科学领域，其与计算机技术相结合也只是近几年的事。国内对SNA的研究相对滞后，从深度和广度两方面都与国外的研究水平有着很大的差距，而且大部分研究论文皆属于社会科学和经济管理领域，与计算机科学直接相关的不足10%，而且大多还停留在初步的理论探讨或简单应用，要想形成良性循环任重而道远。客观上，伴随着中华民族的复兴，作为一个新近崛起的经济大国，中国不仅需要社会科学和经济管理领域领域SNA的研究，也需要与信息时代的计算机技术相结合的SNA的研究，以便能够大幅提高工作效率。开展SNA的研究有利于国家许多方面的发展，例如：利用SNA研究反恐网络，有利于国家安全，美国学者的模拟实验已经证明，如果预先利用基于SNA的反恐网络进行先行处理，则“9.11”事件完全可以被提前终止，新疆“7.5”事件的发生更能说明我国展开这方面研究的迫切性和重要性；利用SNA研究疫情监控，可以保证国家卫生安全，能够快速找出疫情传播的薄弱环节，用最短的时间取得最大的收益。

目前尚无统一和通用的SNA方法应用框架，但美国的CrimeNet Explorer项目中针对犯罪网络提出的框架具有通用的潜质。该框架包括四个主要阶段：网络建立，网络划分，结构分析和网络可视化。这个框架完全勾勒出应用SNA方法的整体轮廓，其中，网络划分是一个NP-hard问题，而且网络划分阶段起到承上启下的作用，所以在整个过程中该阶段占有极其重要的地位。对于社会网络划分研究，国内尚处于起步阶段，国外则刚从同质划分阶段过渡到异质划分阶段。

网络划分也可以称作网络社区识别。但一般来说，网络社区识别具较之前者具有更丰富的内涵。从目前的文献来看，对于网络社区识别这一概念主要有两种理解：一是指利用某种方法将网络划分成内部联系紧密而相互之间联系稀疏的簇，二是指按照某种要求以人机交互的方式将满足要求的社区找出来。网络划分的内涵只局限于社会网络社区识别的第一种理解 中。为使术语具有更强的概括性，本研究中尽量使用社会网络社区识别这一术语。但在个别情况下，如在介绍基于谱聚类的社区识别方法时，社会网络划分显得更自然、更直观，所以在有些地方还会使用网络划分一词。

很多情况下，社会网络社区识别都是在考虑社会行动者之间存在各种关系的情况下，通过对社会行动者进行聚类实现的。大多数的传统聚类方法把研究对象假设为具有相同数据结构的数据对象，即每种数据对象都可以用特定长度的特征向量来描述。但是现实世界中的数据对象的数据结构是复杂多变且不统一的，往往包含多种类型的数据对象并且彼此相互关联。传统聚类算法在应对异质、多关系的社会网络时，常常会遇到许多不可逾越的障碍。

2 社会网络分析的研究

近些年来，国外的学者从理论和实践两个方面对SNA进行了广泛而深入的研究和探讨。为了进行犯罪调查和防止犯罪，帮助法律执行部门和情报机构高效地从犯罪网络中进行知识发现，美国耗费三年时间开发了基于SNA的CrimeNet Explorer，模拟实验证明该软件十分有效。“9·11”之后，反恐网络中的知识发现也一直是外国学者的研究目标，文献中不但对一些恐怖袭击事件运用SNA进行了分析，还证明了如果能够在事件发生之前就应用SNA对网络进行分析，完全可能阻止事件的发生，并将所有罪犯绳之以法；另外，该文献还特别关注了网络的可视化问题。隐私保护是近年来的一个研究热点，Elena Zheleva等人对SNA中的隐私保护问题[3]进行深入的研究，给出了攻击模型。研究作者合作网络也是一个重要的课题，Ulrik Brandes等人利用SNA对维基百科的合作结构[4]进行探讨，提出了描述和分析作者合作结构的模型和算法。BlockModel一直是SNA研究领域一个重要的模型，Edoardo M. Airoldi等人提出混合成员随机块模型[5]，新模型较旧模型有了较大的改进，可应用于蛋白质相互作用网络、基因常规网络、邮件网络等。

目前在Internet 上存在许多社会网络网站，这些网站采集了注册用户的基本信息，并允许这些用户介绍亲朋加入，由此即构成了社会网络，在此基础上还可进一步与享有共同爱好的其他人发展新的友谊关系，Peter Mika研究了社会网络与语义网络的关系，指出了社会网络网站存在的缺陷以及应对的策略。网络的可视化是SNA研究领域的一个重要方面，网络的可视化目的在于使隐藏的网络结构和个体角色等能更清晰、更易于理解的方式展现出来，Fabricio Benevenuto 等人提出一个用于网络可视化的统计模型，并且深入研究了基于视频构建的社区兴趣发现，并在发现投机行为模式的基础上讨论了投机行为对用户间相互信任的损害[6]。博客，以及当下流行的微博，可以帮助人们表达思想、发表观点、分享经验和理念。博客和微博的开放标准以及发表信息的低门槛，使网络社区中蕴含了大量的知识。寻找合适的工具从博客网络社区中发现知识，是一个热点问题。社会网络社区挖掘是SNA的一个重要研究方向，Deng Cai等人给出异质社会网络隐藏社区挖掘的新方法[7]，实验证明该方法非常有效，远远优于传统的挖掘方法。合作关系网络属于大型社会网络之一，网络的进化演变是SNA的重要研究任务。

国内对SNA的研究相对滞后，但在某些领域也取得了一些可喜成果。例如，人名检索结果重名消解问题的研究。众所周知，人物重名现象十分普遍。搜索引擎的人名检索结果通常是多个同名人物相关网页的混合，郎君等人依据同名的不同人物具有不同的社会网络的思想，利用检索结果中共现的人名发现并拓展检索人物相关的潜在社会网络，结合图的谱分割算法和模块度指标进行社会网络的自动聚类，在此基础上实现人名检索结果的重名消解。在人工标注的中文人名语料上进行实验，整体性能达到较好水平[8]。再如，基于社会网络可视化分析的数据挖掘研究，杨育彬等人结合社会网络可视化分析和数据挖掘的理论与方法，引入相关的地理信息，对1980—2002年间世界范围内1417例恐怖袭击事件的数据库进行数据分析，以这些恐怖袭击事件各要素结点之间关系作为基本分析单位，对恐怖组织之间活动模式和发展特点等内在规律进行挖掘与解释，得出一些有意义的结果。提出的方法可以有效地推广应用于蛋白质结构分析、生物基因分析以及各类社会问题的分析过程[9]。

3 社会网络社区识别的研究

针对社会会网络社区识别的研究，国外起步较早且发展比较成熟，先后有 Kernighan-Lin算法、GN算法及其改进算法、主题模型PLSA、作者-主题模型、谱聚类、基于密度的方法、SimRank算法、RankClus算法、NetClus算法等研究成果。Kernighan-Lin算法基于贪婪算法将网络识别为两个大小已知的社区[10]，其最主要的缺陷是如果不能正确指定社区的大小则会造成结点的错分。GN算法则是从网络中依次移除边界数最大的边以实现社区识别，但该算法时间复杂度过高[11]，社区划分质量较差。针对GN算法的缺陷，陆续有一些基于模块度的改进算法被提出[12]，但由于模块度定义的固有缺陷，这些改进算法倾向于将网络识别成由规模相似的社区构成。主题模型PLSA单纯地利用文本信息对网络进行识别，并未考虑对象之间的链接信息。作者-主题模型[13]对PLSA进行了进一步的发展，不但利用了纯文本信息，还通过利用复杂产生模型加入了对象类型信息。对文本信息和图约束的目标函数进行优化组合[14]，也是一种较好的识别方法。以上这几种识别方法都把文本信息作为重要的识别依据，应用范围较小，而且只能应用在同质网络上。

在国内，社会网络社区识别的研究总体上还只局限于基于国外经典算法的改进以对同质网络进行研究；就目前掌握的资料看，尚未发现异质网络上的社区发现研究。最值得注意的研究工作是淦文燕等的基于拓扑势的社区发现研究[15]，该研究提出的识别方法具有较高的准确率，但该研究也是基于同质网络的。

4 结语

随着信息技术的发展和普及，传统的社会成员之间因互动而形成的社会关系已经延伸到虚拟网络环境中。社会网络不仅为人们提供了交友娱乐的平台，而且逐渐成为辅助行政、商务等活动的有力工具，成为一种新型的协同工作方式。同时，为了完善和改进社会网络的沟通和交互机制，各种协同技术也应用到社会网络中。本文针对以上情况对社会网络分析和社区结构识别这两项重要的研究内容进行了总结，以起到抛砖引玉的作用。

[参考文献]

[1] Jennifer Xu, Hsinchun Chen. CrimeNet Explorer: A Framework for criminal network knowledge discovery[J]. ACM Transactions on Infromation Systems, 2005, 23(2): 201-226.

[2] Jennifer Xu, Hsinchun Chen. Criminal Network Analysis and Visualization[J]. Communications of the ACM, 2005, 48(6): 100-107.

[3] Elena Zheleva, Lise Getoor. To Join or Not to Join: The Illusion of privacy in social networks with mixed public and private user profiles[C]// IW3C2, 2009: 531-540.

[4] Ulrik Brandes, Patrick Kenis, Jürgen Lerner, et al. Network analysis of collaboration structure in Wikipedia [C]// Proceedings of the 18th International Conference on World Wide Web, 2009: 731-740.

[5] Edoardo M. Airoldi, David M. Blei, et al. Mixed membership stochastic block models[J]. Journal of Machine Learning Research, 2008: 1981-2014.

[6] Fabricio Benevenuto, Tiago Rodrigues, Virgilio Almeida, et al. Video interactions in online video social networks[J]. Transactions on Multimedia Computing, Communications, and Applications, 2009, 5(4): 1-30.

[7] Deng Cai, Zheng Shao, Xiaofei He. Mining hidden community in heterogeneous social networks[C] // Proceedings of the 3rd international workshop on Link discovery, 2005: 58-65.

[8] 郎君, 秦兵, 宋巍，等. 基于社会网络的人名检索结果重名消解[J]. 计算机学报, 2009, 32(7): 1355-1374.

[9] Yang Yu-bin, Li Ning, Zhang Yao. Networked data mining based on social network visualizations[J]. Journal of Software, 2008, 19(8): 1980-1994.

[10] Kernighan B W, Lin S. A efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49: 291-307.

[11] Girvan M, Newman M E J. Community structure in social and biological networks[C] // Proc. Natl. Acad. Sci., 2001,99:7821-7826.

[12] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Phys. Rev. E., 2004,69: 1-16.

[13] M. Steyvers, P. Smyth, M. Rosen-Zvi, et. al. Probabilistic author-topic models for information discovery[C] // In KDD’04, 2004: 306-315.

[14] Q. Mei, D. Zhang, C. Zhai. A general optimization framework for smoothing language models on graph structures[C]// In SIGIR’08, 2008: 611-618.

[15] 淦文燕, 赫南, 李德毅，等. 一种基于拓扑势的网络社区发现方法[J]. 软件学报, 2009, 20(8): 2241-2254.