社会网络分析中的数据挖掘综述

社会网络分析中的数据挖掘综述

张引∗ (南京大学 计算机科学与技术系, 南京 210093)

Data Mining in Social Network Analysis: A Survey

ZHANG Yin*

(Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China)

Abstract: The application of techniques from data mining into social network analysis provides a new direction for the research of data mining. Different from the traditional tasks of data mining, which assume the instances are independent, instances in social network are dependent. Such dependence can be described as links. Mining from links can provide us more accurate and richer information about the social network. This paper briefly introduces 7 common link mining tasks based on their types. Key words:

social network analysis; data mining; link mining

摘 要: 将数据挖掘的方法应用于社会网络分析是数据挖掘研究的一个新的方向。与传统数据挖掘研究的对象不同，在社会网络分析中个体之间由于存在着相互的联系，故不满足独立的假设，个体之间这种相互的联系就是链接。对链接信息的挖掘，即链接挖掘，可以给我们提供关于这个社会网络更丰富更准确的信息。本文按照链接挖掘的种类简要介绍了其中7个主要的研究热点任务。 关键词: 社会网络分析; 数据挖掘; 链接挖掘 中图法分类号: TP301 文献标识码: A

1 引言

传统的机器学习和数据挖掘任务处理的对象是单独的数据实例，这些数据实例往往可以用一个包含多个属性值的向量来表示，同时这些数据实例之间假设是统计上独立的。例如要训练一个疾病诊断系统，它的任务是诊断一个被试者是否患有某种传染病。传统的学习算法用一个向量来表示一个被试者，同时假设两个被试者之间的患病情况是相互独立的，即知道一个确诊病人对于诊断其他被试者是否患病不能提供任何帮助。直观经验告诉我们这种假设是不合理的，一个人的亲戚、朋友患有此传染病，则他相对其他人有更大的可能性患病。在社会里，人与人不是简单的统计上独立的采样点，他们之间必然存在着联系和影响。忽视了这种联系会对这个诊断系统的性能带来很大的影响。为了解决这个问题，必须将数据实例之间的关系同时考虑进来，从而人们提出了社会网络的概念，试图用图结构来刻画这种社会结构。一个社会网络由很多节点（node）和连接这些节点的一种或多种特定的链接（link）所组成。节点往往表示了个人或团体，也即传统数据挖掘中的数据实例，链接则表示了他们之间存在的各种关系（relation），如朋友关系、亲属关系、贸易关系、性关系等。与传统的数据挖掘只关注数据实例不同，社会网络分析对链接同样关注。从数

∗ 作者简介: 张引（1985-），男，浙江舟山人，硕士研究生，主要研究领域为机器学习和计算机视觉

2

据挖掘角度，社会网络分析又称为链接挖掘（link mining）[38]。通过对链接的挖掘我们可以获得关于实例更丰富（如某个实例在整个网络中的重要性）、更准确（如预测某个实例所属的类别）的信息。与此同时，很多时候链接本身也是我们所关心的信息，如在某些情况下，并不是所有的链接都被观测到，因而我们可能对预测实例之间的链接是否存在感兴趣。在其他领域，链接随着时间不断转变，那么我们的目标可能是基于当前的观察来预测在未来某个时刻某个链接是否存在。更深入地，由于考虑了数据之间的链接，社会网络的结构属性，如节点的度数（degree）、连通性（connectivity）在挖掘中也提供了重要信息，同时，更复杂的模式，如子图（subgraph）（可理解为社团或群体等）随之出现，如何获得关于这些模式的更复杂的信息也给链接挖掘提出了更大的挑战。

由于链接挖掘包括了很广泛的任务，这篇综述只能介绍在这些任务中较为核心的研究热点。本文其他部分的结构如下：第二部分分析了链接挖掘中社会网络数据的表示形式及其存在的问题；第三部分根据挖掘任务侧重点的不同（节点、链接、图）将它们分成七种（参见表1）分别介绍；最后总结全文。

表1 常见的链接挖掘任务及其分类

节点相关任务 链接相关任务

图相关任务

基于链接的节点排序（Link-Based Object Ranking） 基于链接的节点分类（Link-Based Object Classification） 节点聚类（Object Clustering） 链接预测（Link Prediction） 子图发现（Subgraph Discovery） 图分类（Graph Classification）

图的产生式模型（Generative Models for Graphs）

2 链接挖掘中的数据表示

为了做到有效的链接挖掘，首先要将社会网络形式化。图论中的图（graph）为形式化社会网络提供了直观的表示形式。Freeman 提出了社会网络分析必须具备的四个特征[1]：

1. 2. 3. 4.

社会网络分析更注重行动者(Actor)之间的联系，而不是行动者本身所具有的性质； 关于行动者之间联系(tie)的数据必须通过系统化的方法收集； 建立在图模型之上；

使用数学和计算工具来从这些关系中获取有意义的信息。

第三点明确告诉我们，图作为社会网络为基本的表示是合适的。社会网络就是由行动者（即图中的节点）和行动者之间的联系（即图中的链接）组成的，其中

行动者(Actor)：社会实体，可以表示具体的个人，社团及其它集体社会单元。

联系(Relation tie)：不同的社会实体通过联系连接在一起。在不同的网络中，其意义也不同。例如：一个人对另一个人的评价，物质资料在实体间的转移，实体间的行为互动，两者的合作关系等等。

除了以上两种基本元素之外，更复杂的模式包括：

二元组(Dyad)：由两个行动者及他们之间的关系组成，这是研究关系模式的基本单位；

子图(Subgroup)：由网络中的一部分行动者和他们之间的关系组成，可以通过子图来研究社会网络中的一个小团体所具有的特征；

图(Graph)：所有行动者及其之间的关系，分析社会网络的总体特征。

然而这种直观的表示并不意味着链接挖掘中的数据表示的确很简单。为了说明这种表示存在的缺陷，我们可以考虑一个描述了行动者和他们所参与的事件的社会网络[2]。如果用表结构表示，这个社会网络可以很容易表示为三个表：行为者表、事件表和参与关系表。如果用图结构表示，一个自然地表示可以用二分图：一个集合包含行为者节点，一个集合包含事件节点。连接这两个集合中的点的边表示了行为者的参

3

与关系，即如果一个行为者参与了一个事件，则这个行为者节点和这个事件节点之间就存在一条边，反之则没有边。然而我们还可以采用其他的表示，从另一种视角看待这个社会网络。如我们可以以行为者为节点，两个行为者之间的边则表征了这两个行为者参与了同一个事件。这种表示使我们的分析能更加以行为者为中心。另一方面，如果我们把事件作为节点，两个事件之间的链接表征了有行为者参与了这两个事件，那么这种表示使我们的分析更加以事件为中心。对于存在多种节点和链接的社会网络，这样的表示形式会更多。尽管一般认为表示的选择不是链接挖掘的一部分，但它对挖掘中的统计推断有着非常重要的影响。所以为解决一个具体社会问题，合理地选择社会网络表示形式对于好的链接挖掘系统是非常关键的。在下面部分的链接挖掘的介绍中我们假设已经选取了合适的表示。

3 典型链接挖掘任务介绍

3.1 基于链接的节点排序

基于链接的节点排序是社会网络分析中一个核心分析任务[3]，它的目的是通过分析利用图中的链接结构，根据某种衡量节点重要性的度量来对图中节点进行排序，这种可度量的重要性被称为中心度（centrality）。根据复杂程度的不同，它们可分为局部度量和全局度量。其中前者包括“度中心度”（degree centrality）[4]，即个顶点的度数，后者包括“特征向量/能量中心度”（eigenvector/power centrality）[5]，即通过谱方法（Spectral methods）根据一个节点到其他重要节点的连接来刻画该节点的重要性。

除了上述基于在静态图上用给定的度量进行全局排序的工作外，对相对于图中若干相关节点的局部节点排序[6]和在动态图上的节点排序[7]也同样引人注目。Jeh和Widom [6]提出了一种估计两个节点间相似程度的新的度量，这种度量基于这两个节点到他们所链接的相似节点的度数。在他们的文章中，这种相似度是通过随机游走来计算的。Sun等人[8]则在此基础上引入了图分块以提高算法的稳定性。在动态图上排序考虑了事件的时间信息，这种考虑是必要的，如电子邮件、电话或者文献发表情况。与静态图上的排序不同，动态排序的目标是追踪节点随着新事件发生的排序变化O'Madadhain等人[7]关于这个问题提出了一系列需要满足的算法性质，讨论了静态排序算法的局限性并引入了基于潜流（potential flow）的满足上述要求的排序算法。

3.2 基于链接的节点分类

传统机器学习中的分类问题是基于数据实例（节点）是独立同分布的假设，然而很多现实问题不满足这个假设。在基于链接的节点分类问题中，一个数据图G = (O;L) 表示了节点集合O和他们之间的链接集合L，我们的任务是将O中的成员赋予某一类标签。基于链接的节点分类与传统分类问题的最显著的不同在于节点的类别是彼此相关的。如何设计合理的分类算法能有效地利用这些相关信息是研究者所面临的挑战。Chakrabarti等人[9]最早在Reuters新闻数据集上考虑了这个问题。Lafferty等人[10]提出了条件随机场(Conditional Random Fields)的概念，扩展了传统最大熵模型对于数据的结构必须是链式结构的限制。Lu和Getoor[11]通过对每个数据实例增加新的属性来扩展简单的机器学习分类器，目的是使其能处理基于链接的节点分类问题。增加的新属性度量了类标签在节点组成的马尔可夫毯（Markov blanket）中的分布。

除了机器学习的研究者外，计算机视觉、自然语言处理的研究者由于各自的应用需要同样关注基于链接的节点分类问题。Chakrabarti等人[13]利用Rosenfeld等人[12]提出的放松标签（relaxation labeling）概念实现了基于链接的节点分类中的推断算法。Lafferty等人[10] 将条件随机场用于词性标注。 3.3 节点聚类

节点聚类又称为群体检测（Group Detection），它的目的是将有着共同的特征的节点聚类。首先假设图中的节点和链接都属于同一种类。在这种假定下，群体检测的技术可以分成聚合聚类和分裂聚类两种。社会网络分析中块建模（blockmodeling）的任务是将社会网络分割成个体的集合，这种集合称为位置（position），显示了在网络中相似链接的集合[4]。一种定义在链接集合和聚合聚类之间的相似度量被用来寻找位置。谱

4

图分割的方法（Spectral graph partitioning methods）用确定为了使图达到指定数量群体而可以去掉的近似最小链接集合来解决群体检测问题[14]。最近的另外的群体检测方法利用了一种刻画边的连接的度量来确定连接群体的链接[15]。这种想法源于Freeman关于连接中心度（betweenness centrality）的观点[4]。为了分割图，有较高的边连接度的链接不断地被从图中删去。

与上述确定地群体指派的方法不同的，很多群体检测的方法是基于社会网络分析中的随机块建模（stochastic blockmodeling）。在随机块建模中，观测到的社会网络被假设为对依赖的随机块模型的一种实现[3]。个体在网络中的位置假定是满足独立同分布的随机变量，给定类型的关系链接只依赖于它所连接的两个个体的位置。Nowicki和Snijders[16]提出了一种一般化的随机块建模的方法，可以处理有向、带权值的关系和任意多的位置数。推测位置的后验概率则采用了Gibbs采样。Kemp等人[17]去掉了预先指定位置数的要求，位置数可以从数据中直接推测出来。Wolfe和Jensen[18]扩展了一般的随机块建模的方法，允许一个个体有多个位置类型。对于一个个体在不同环境下有不同角色的建模问题，这种方法提供了很大的便捷。 3.4 链接预测

链接预测是基于它所链接的节点属性和已观测到的链接来预测某链接是否存在。链接预测的应用非常广泛，包括预测社会中人与人之间的朋友关系，电子邮件、电话联系，合作关系等。往往一些链接被观察到，未被观察到的需要我们去推测；或者存在一个时间序列，在某个时间点t的连接状态已知，要预测t+1时间点的链接状态。这个问题经常被看成是一个简单的两类分类问题：对于可能有连接存在的两个节点oi和oj ，预测lij是1还是0。一种方法是完全基于网络的结构信息进行预测。Liben-Nowell和Kleinberg[19]提供了在不同图近似尺度下的预测的综述。其他的方法在进行链接预测时使用了属性信息。Popescul等人[20]引入了一种结构逻辑回归模型（logistic regression model），这种模型可以利用关系特征（relational features）来预测链接的存在。关系特征的定义是由数据库查询引入的，作者显示了如何搜索关系特征空间。O'Madadhain等人 [7]则基于属性和结构特征构造了局部条件概率模型。

由于多数我们感兴趣的数据集是稀疏的，因而链接预测是比较困难的。为链接预测构造统计模型的一个难点在于，链接的先验概率往往很低。这种困难不仅在于模型评价中，也在于预测可行程度的定量。一种提高预测质量的方法是使预测全体化。很多方法在整个链接的图、标签和边上构造一个概率模型。这些网络结构的联合模型经常基于马尔可夫随机场（Markov random fields）[21]等模型。最简单的情况，有节点集合O，属性集X，边集E ，MRF建模了在边集E上的联合分布P(E)，或者基于节点属性的条件分布P(Ej|X)。更复杂的基于关系表示的模型包括关系马尔可夫随机场（Relational Markov Networks）[22] 和最近提出的马尔可夫逻辑网（Markov Logic Networks）[23]等。基于有向图的模型也是可行的。Getoor等人[24]描述了处理概率关系模型中链接不确定性的方法。这个方法一个区别于先前方法的特点是它在链接上做概率推断，这样可以得到边之间的相关信息。理想情况下这种方法能得到更准确的预测。然而基于模型的概率方法有着计算代价高的问题，准确的推测往往是不可行的，所以需要近似推断。 3.5 子图发现

子图发现的任务是在一个图的集合中找到感兴趣的或者频繁出现的子图。这种模式的发现可以作为系统中单独的任务，也可以用于3.6节中的图分类。

一个研究方向的是在图中寻找频繁子图。最简单的匹配要求子图同构的测试，因而有效的近似算法是必需的。Inokuchi等人[25]描述了AGM，它寻找了所有满足最小支持的归纳子图。Kuromachi等人[26]利用一种子图数据的邻接表示和描述新的优化的候选子图生成过程来改进AGM。Yan等人[27]描述了 gSpan，这种方法避免了候选子图生成的代价。它首先将每一幅图映射到深度优先搜索编码，并用字典序排序。然后在这个字典序定义的搜索树上进行深度优先搜索。其他的方法来自于归纳逻辑编程（Inductive Logic Programming）。Dehaspe等人[28]最早成功地将ILP的技术应用于在毒物学领域寻找频繁模式。

另一个方向的研究关注有效的生成子图和基于压缩的启发式搜索。Subdue[29]，在这个领域最早的工作，利用基于MDL的启发式来指导子图的搜索。Subdue被用于子图发现和图分类。另一个例子，基于图的归纳

5

（Graph-Based Induction）通过将频繁出现的顶点组合成块来压缩输入的图。这两种方法都在搜索频繁子结构中使用了局部贪婪方法。Ketkar等人[30]比较了这些方法和ILP。 3.6 图分类

󰀂不同于基于链接的节点分类，图分类是一种试图将整张图用正或负标签来分类的监督学习问题。这是最早的将机器学习和数据挖掘技术应用与图数据的任务。图分类一般不要求像节点、边分类中要求的集体推断。这是因为图一般是假设独立的。三种主要方法有：基于图上特征挖掘，归纳逻辑编程（ILP）和定义图核函数。

图上特征挖掘使用了类似于3.5节子图发现的方法，因为图上特征挖掘的一般做法是在图实例中寻找所有频繁或者有意义的子图。这些子结构被用于将图数据转化成一个单表的数据表示，然后传统的分类算法可以将图实例进行分类。

一个ILP方法的例子，King等人[31]首先将用于描述变异的图数据影射成关系表示。他们用逻辑的关系表示如vertex(graphId,VertexId,VertexLabel, VertexAttributes)和edge(graphId,vertexId1,vertexId2,BondLabel)，然后用一个ILP的系统来在这个假设空间中寻找一个合理的假设。

寻找频繁子结构在计算上往往是不可行的。一个替代的算法使用了核方法。Gartner和Kashima基于一种在图上的游走的度量来描述了图核函数[32;33]。Gartner[33]计数了起点和终点有相同标签的游走。Kashima[32]则考虑了有着相同标签序列的随机游走的概率。Gartner[34]综述了结构数据中的核方法。 3.7 图的产生式模型

不同的依赖类型的图的产生式模型在社会网络分析中已经被深入的学习。对于单节点和链接类型的有向图，有多种随机图分布，如：Bernoulli图分布，条件一致（conditional uniform）图分布，二值依赖（dyadic dependence）图分布和P*模型等。Bernoulli 图是到现在位置最简单的产生式模型，它假设指示节点oi和oj之间有向边是否存在的随机变量{lij}是独立同分布的。当连接存在概率为0.5时，这个分布往往被称为一致随机图分布。条件一致图分布定义为在有着特殊结构特征的图集合上的一致分布。这些特殊的特征诸如固定的链接书、入度、出度等。二值依赖分布假设只有二元组(lij; lji)是相互依赖的，并且这些二元组满足多项式分布。P*模型假设那些至少有一个公共顶点的链接相互依赖。产生式模型所允许的依赖结构比马尔可夫图模型更广泛，包括多节点、链接类型和链接结构和节点数变化的动态网络模型[35]。

最近关于如万维网、在线社会网络、交际网络、引用网络和生物网络的网络结构性质的研究受到了很大的关注。在这些不同的网络中，普遍的模式如能量准则度分布、小图直径和交际结构等被观测到。这些观测到的信息激励研究者寻找一种一般的准则来管理这种网络。对于这个问题，Airoldi等人[5]回顾了对于很多常见的网络类型，如刻度无关的网络、小世界网络、核心-外围网络和细胞网络能显示出这种性质的采样算法。与社会网络分析中的随机处理模型不同，多数的产生式模型是被指定了在某种特定的过程形式。这被认为是有利于理解诸如能量准则度分布是如何随时间自然在动态网络里出现的问题。

4 总结

社会网络分析由于不满足数据的独立同分布假设，因而给数据挖掘的研究提出了新的挑战，并产生了一个新的方向：链接挖掘。在这篇文章中我们概述了在链接挖掘中几个相对成熟的研究任务：基于链接的节点排序、基于链接的节点分类、节点聚类、连接预测、子图发现、图分类和图的产生式模型。他们代表了这个新兴研究在越来越广泛的应用领域的共同趋势。 References:

[1] L. Freeman, The Development of Social Network Analysis: A Study in the Sociology of Science, Empirical Press, Vancouver, BC,

2004.

6

[2] L. Singh, L. Getoor, and L. Licamele. Pruning social networks using structural properties and descriptive attributes. In

International Conference on Data Mining, 2005.

[3] S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994. [4] L. Freeman. Centrality in social networks: Conceptual clarifications. Social Networks, 1:215-239, 1979.

[5] P. Bonacich. Power and centrality: A family of measures. American Journal of Sociology, 92(5):1170-1182, 1987.

[6] G. Jeh and J. Widom. SimRank: A measure of structural-context similarity. In ACM SIGKDD International Conference on

Knowledge Discovery and Data Mining, pages 538-543, 2002.

[7] J. O'Madadhain, J. Hutchins, and P. Smyth. Prediction and ranking algorithms for even-based network data. SIGKDD

Explorations, 7(2), December 2005.

[8] J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos. Relevance search and anomaly detection in bipartite graphs. SIGKDD

Explorations, 7(2), December 2005.

[9] S. Chakrabarti, B. Dom, and P. Indyk. Enhanced hypertext categorization using hyperlinks. In SIGMOD International Conference

on Management of Data, pages 307-318, 1998.

[10] J. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence

data. In Proc. of ICML-01, 2001.

[11] Q. Lu and L. Getoor. Link-based classification. In International Conference on Machine Learning, 2003.

[12] A. Rosenfeld, R. Hummel, and S. Zucker. Scene labeling by relaxation operations. IEEE Transactions on Systems, Man and

Cybernetics, 6(6), 1976.

[13] S. Chakrabarti, B. Dom, and P. Indyk. Enhanced hypertext categorization using hyperlinks. In SIGMOD International Conference

on Management of Data, pages 307-318, 1998.

[14] M. E. J. Newman. Detecting community structure in networks. European Physical Journal B, 38:321-330, 2004.

[15] J. R. Tyler, D. M. Wilkinson, and B. A. Huberman. Email as Spectroscopy: Automated Discovery of Community Structure within

Organizations. Kluwer, B.V., Deventer, The Netherlands, The Netherlands, 2003.

[16] K. Nowicki and T. A. B. Snijders. Estimation and prediction for stochastic blockstructures. Journal of the American Statistical

Association, 96(455):1077-1087, 2001.

[17] C. Kemp, T. L. Griffiths, and J. B. Tenenbaum. Discovering latent classes in relational data. Technical Report AI Memo 2004-019,

Massachusetts Institute of Technology, September 2004.

[18] A. P. Wolfe and D. Jensen. Playing multiple roles: Discovering overlapping roles in social networks. In ICML-04 Workshop on

Statistical Relational Learning and its Connections to Other Fields, 2004.

[19] D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In International Conference on Information

and Knowledge Management (CIKM), pages 556-559, 2003.

[20] A. Popescul and L. H. Ungar. Statistical relational learning for link prediction. In IJCAI Workshop on Learning Statistical Models

from Relational Data, 2003.

[21] R. Chellappa and A. Jain. Markov random fields: theory and applications. Academic Press, Boston, 1993.

[22] B. Taskar, M.-F.Wong, P. Abbeel, and D. Koller. Link prediction in relational data. In Neural Information Processing Systems

Conference, Vancouver, Canada, December 2003.

[23] P. Domingos and M. Richardson. Markov logic: A unifying framework for statistical relational learning. In ICML-2004 Workshop

on Statistical Relational Learning and its Connections to Other Fields, pages 49-54, 2004.

[24] L. Getoor, N. Friedman, D. Koller, and B. Taskar. Learning probabilistic models of link structure. Journal of Machine Learning

Research, 3:679-707, 2003.

[25] A. Inokuchi, T. Washio, and H. Motoda. An Aprioribased algorithm for mining frequent substructures from graph data. In

European Conference on Principles and Practice of Knowledge Discovery and Data Mining, pages 13-23, 2000.

[26] M. Kuramochi and G. Karypis. Frequent subgraph discovery. In IEEE International Conference on Data Mining, pages 313-320,

2001.

[27] X. Yan and J. Han. gSpan: Graph-based substructure pattern mining. In International Conference on Data Mining, 2002.

[28] L. Dehaspe, H. Toivonen, and R. King. Finding frequent substructures in chemical compounds. In International Conference on

Knowledge Discovery and Data Mining, pages 30-36, 1998.

7

[29] D. J. Cook and L. B. Holder. Substructure discovery using minimum description length and background knowledge. Journal of

Artificial Intelligence Research, 1:231-255, 1994.

[30] N. Ketkar, L. Holder, and D. Cook. Comparison of graph-based and logic-based multi-relational data mining. SIGKDD

Explorations, 7(2), December 2005.

[31] R. D. King, S. H. Muggleton, A. Srinivasan, and M. J. E. Sternberg. Structure-activity relationships derived by machine learning:

The use of atoms and their bond connectivities to predict mutagenicity by inductive logic programming. National Academy of Sciences, 93(1):438-442, January 1996.

[32] T. Gartner. Exponential and geometric kernels for graphs. In NIPS Workshop on Unreal Data: Principles of Modeling

Nonvectorial Data, 2002.

[33] H. Kashima and A. Inokuchi. Kernels for graph classification. In ICDM Workshop on Active Mining, 2002. [34] T. Gartner. A survey of kernels for structured data. SIGKDD Explorations, 5(1):49-58, 2003.

[35] P. J. Carrington, J. Scott, and S. Wasserman. Models and Methods in Social Network Analysis. Cambridge University Press,

Cambridge, 2005.

[36] E. M. Airoldi and K. M. Carley. Sampling algorithms for pure network topologies. SIGKDD Explorations, 7(2), 2005. [37] L. Getoor, Link mining: A survey. ACM SIGKDD Explorations Newsletter, 2005, 7(2):3-12.

[38] J. W. Han and M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000.