基于社交网络节点中心度挖掘其社区框架

王童童　李盛恩　王　刚

(山东建筑大学计算机科学与技术学院　山东 济南 250101)



基于社交网络节点中心度挖掘其社区框架

王童童李盛恩王刚

(山东建筑大学计算机科学与技术学院山东 济南 250101)

摘要社区结构作为真实复杂网络所普遍具有的一个重要的拓扑特性，最近10年内得到了广泛而深入的研究。为解决社区挖掘策略时间复杂度过高、缺少与用户交互等问题，讨论了社交网络节点中心度、度的幂律分布等特性，提出了“关键子网络”和“社区框架”的概念，设计了社区框架挖掘算法MCF(Mine the Community Framework)和社区框架钻取算法DCF(Drill Down the Community Framework)，其中MCF算法用于挖掘社交网络的社区框架，DCF用于对社区框架进行钻取，从不同粒度展现社区结构。实验结果和实验分析表明，MCF算法能够在较短时间内挖掘出反映复杂网络社区状态的社区框架，DCF算法可以以用户交互方式实现高质量的社区划分。

关键词社交网络社区结构节点中心度社区框架社区质量

0引言

真实世界中的许多复杂系统可以表示成图或者网络，包括社交网络、信息网络、生物网络和技术网络等[1]。经验分析表明，这些复杂网络往往是由若干个节点组构成，节点组内部的连接相对紧密，而节点组之间的连接却相对比较稀疏。我们称网络的这种拓扑特性为社区结构，相应地，每个节点组被称为一个社区。不同的应用领域，社区结构具有不同的内涵。比如，社交网络中一个社区代表了具有相似特征的人群；生物网络中的社区解释了具有相似功能的生物组织模块；Web网络中的文档类簇包含了大量的具有相关主题的Web文档等[2]。社区挖掘就是对这些不同类型复杂网络进行处理，挖掘出社区结构，从而来帮助人们理解复杂网络的功能，发现复杂网络中隐藏的规律和预测复杂网络的行为[3]。

虽然现在发展出了大量的社区挖掘策略，例如GN算法[4]、谱分解算法[5]等，然而这些社区挖掘算法大部分都是直接针对完整社交网络数据进行社区挖掘。例如GN需要反复计算整个网络的任意两点的最短路径，谱分解算法需要将每一个节点在向量空间中加以表示。这样的处理策略还存在不足之处：首先，使用社区挖掘策略对一个很大的社交网络进行社区挖掘需要大量的计算，计算时间长，例如GN算法时间复杂度为O(n2m)，谱分解算法为O(n2)，其中n为节点个数，m为边的条数；其次，即使挖掘出社区结构，这个社区结构将涉及所有点的信息，社区结构过于复杂；最后，这些社区挖掘策略在设置完初始参数后，就开始计算，然后返回给用户整个网络的社区划分，计算过程中，用户不能进行控制，缺乏交互。

文献[6,7]指出在社交网络中存在少部分的节点中心度较高的节点，其构成的子网络能够反映整个社交网络的拓扑特性。为了能够快速对社交网络进行社区挖掘，并且让用户能够控制挖掘的粒度，受其启发我们提出了关键子网络的概念，进而提出了MCF算法和DCF算法。MCF算法利用社交网络的节点中心度提取出社交网络的关键子网络，关键子网络的结点数和边数远小于原社交网络，同时保持了原社交网络的拓扑特性。然后利用经典的挖掘算法对关键子网络进行社区挖掘，将获得的社区框架作为整个社交网络的社区概况，这样可以在很大程度上减少计算量，缩短计算时间。用户如果想获得社区结构的更详细信息，可使用DCF算法对社区框架添加一些节点。然后再进行计算，这样在用户的控制下，逐步得到整个社交网络的社区划分，这种挖掘方式类似于在商务智能领域获得成功的OLAP中的下钻操作。

1社交网络与社区结构

社交网用无向图G(V,E)来表示，其中V表示参与社交网络的参与者，E表示参与者之间的关系。对于一个无向图，在计算机中我们可以使用邻接矩阵来表示：

(1)

从邻接矩阵A可知，如果节点i和节点j之间存在联系，则Aij与Aji都为1，否则都为0，所以邻接矩阵A是一个对称矩阵。若求得了一个社交网络的邻接矩阵A，就能够很容易计算出每个节点的度：设定 1n是一个n维并且每一个元素都为1的列向量，则度向量K=A·1n指明了每一个节点的度，其中Ki为节点i的度。

随着对各种网络的深入研究，发现许多实际网络都存在社区结构，Newman等人给出了社交网络社区结构的定义：社区是社交网络中的子网络，子网络内部联系紧密，子网络之间联系稀疏[8]。如图1的社交网络体现了①②③三个社区，通过观察能够发现，在社区内部边的密度要大于社区之间边密度。

图1　社区结构示意图[8]

社交网络的一个社区，往往反映了在这个社交网络中，具有共同兴趣爱好，或者其他共同特性的一群个体。通过研究社交网络的社区结构我们能够了解社交网络的深层结构，及其内部错综复杂的关系。为此发展出了很多的社区结构发现策略，基于其原理可分为基于划分的、基于模块性优化、基于标签传播、基于动力学和基于仿生计算的方法等[9]。

然而对于同一个社交网络我们应用不同的社区划分方法会得到不同的社区划分，即使使用相同的社区挖掘策略有时也会得到不同的社区划分，为了衡量对一个网络社区划分的好坏，基于社区内部联系紧密社区之间联系稀疏的思想，Newman和Girvan提出了著名的模块度函数即Q函数[10]。其定义为：

假定社交网络被某种挖掘策略分解成n个社区，定义一个n×n的对称矩阵E=(eij)。其中eij表示社交网络中位于社区i和社区j之间的边数占总边数的比例；E中对角线上的元素之和称为该矩阵的迹，即：Tre=∑ieii，它表示社交网络中位于社区内部的边数占总边数的比例；定义矩阵E中每行或者每列中各个元素之和为ai=∑eij，它所表示社交网络中与第i个社区中节点相连的边在所有边中所占的比例。在此基础上定义网络划分的模块度为：

式中‖e2‖表示矩阵e2中所有元素之和。Tre表示网络中位于社区内部边数所占图中总边数的比例，‖e2‖表示社区内部边数所占总边数比例的期望。如果社区内部边数的比例不大于任意连接时的期望值则Q=0。Q的最大值为1，Q越接近1，则说明网络的社区划分的质量越好，即社区内部联系越紧密。在实际网络中该值通常位于0.3到0.7之间。

模块度函数表示在节点上的式子为：

(2)

其中P为社区挖掘算法所发现的社区的集合，m为社交网络中边的条数。若节点i和j其度分别为ki与kj，则(ki×kj)/2m计算了两节点之间有边的概率，因此公式中减数部分计算了社区内部边的条数的期望。

2社区框架的挖掘及钻取

现实世界中，我们发现每一个社区中都有很多在该社区中具有重要地位的焦点人物，他们管理组织社区并经常与其他社区的参与者互动。通过对这些重要参与者的社区考察，我们能够总结出整个网络的社区状态。例如在合著网络中，每一个领域都有很多顶尖学者，可以将这些学者提取出来构成一个网络来对其进行社区划分，用以反映整个网络的社区状态。我们提取的由重要参与者构成的网络叫做原社交网络的关键子网络，其社区划分称之为社区框架。当想获得更多社区细节时，我们可以向社区框架中添加节点进行钻取。

2.1节点中心度

中心度就是用来评价一个社交网络中节点重要性的概念。它是关于参与者在社交网络中的中心型位置的测量概念，反映的是不同参与者在社交网络中位置或者优势的差异[6]。现在已经存在很多对社交网络中心度进行测量的方法，有些侧重于局部的参与者，如局部点中心度；有些侧重整体网络结构，如总体中心度。局部点中心度简称为点中心度，其所反映的是某个节点的关系的集中程度，或者是说一个参与者在社会网络中的主导情况，点中心度越大，此参与者越居于中心位置。总体中心度指的是某节点在整个网络结构中与其他各个节点的距离，它所反映的是各个参与者之间的关系密切程度，通常使用节点之间的最短路径来进行衡量。本文主要关注的是某参与者的局部主导性，因此我们将采用节点中心度作为衡量其重要性的标准。

由于核心节点处于社交网络关系中的核心位置，与很多节点存在多种形式的直接连接，所以可以运用社交网络中各节点的度数，对节点的节点中心度做最简单的测量。我们可以通过下面的公式对任意节点i的节点中心度进行计算：

(3)

节点的节点中心度越大，代表其越是该网络的核心节点。

2.2度的幂率分布

19世纪，著名的经济学家Pareto在研究了个人财富的统计分布后，提出了著名的帕累托定律(20/80法则)，即80%的社会财富仅仅掌握在20%的人手中。个人财富值X不小于某个特定数值x的概率与x的常数次幂存在着反比关系：

P(X≤x)～k-γ

(4)

1932年，哈佛大学的语言学家Zifi发现如果将单词出现的频率按照由小到大的顺序进行排列，则每个单词出现的频率和其序号存在着类似于帕累托定律的分布：P(k)～k-γ，这就是著名的Zifi分布。在社交网络、万维网、以及新陈代谢网络等网络中度的分布同样具有这种幂律分布特性P(k)～k-γ(通常2≤γ≤3)[7]，其中P(k)为度数为k的节点占总节点个数的比率。例如，好莱坞演员合作网络的度分布中γ=2.3；www万维网的度分布中γ=2.1；美国西部电力网络的度分布中γ=4。

2.3社区框架的挖掘

(5)

其中函数max(V)计算了社交网络的最大度数，Vk为度为k的节点集合。当取得该关键子网络后我们可以使用已有社区挖掘策略对其进行社区挖掘获得其社区划分，得到的社区划分称之为原社交网络的社区框架。算法描述如算法1。

我们称算法1为MCF算法，在之后的实验中验证了该社区框架能够反映一个社交网络的社区结构概况，如社交网络中每个社区的相对大小，社区内的联系紧密程度以及不同社区之间的联系情况。

算法1MCF(G,r)

1.输入社交网络数据G，比率r

4.输出社区框架P

2.4社区框架的钻取

在得到社区框架后，如果想得到社交网络社区结构更加详细的信息，可以对社区框架进行钻取，即向社区框架中添加度数较小的点。对于一个新添加的点，为了判定其属于社区框架的哪一个社区，需要定义一个距离函数来进行判断。一种最简单的方式是如果新加入的节点i与社区框架中某一社区p中相连的点有d′个，则节点i到社区的距离为d(i,p)=d′。但是，按其定义如果节点i与社区p越远，其联系越紧密，这与直观感觉是相互违背的。因此，定义社区p与节点i的距离为p中与i相连点的个数d′的倒数，即：

(6)

在对社区框架进行钻取时，首先向社区框架中添加不属于社区框架的，但是度数相对于其他节点最大的节点集合Vk，即：

Vk={i|i∈V且i∉V′且ki=max(V-V′)}

(7)

其中函数max(V-V′)求得节点集V-V′中节点的最大度数。Vk添加完成，则新产生的社区框架较原社区框架包含更多的社区结构信息。如想获得社区结构更进一步的信息，则对社区框架继续添加节点，最终直至将所有节点添加进去，实现对整个网络的社区划分，算法描述如算法2。

算法2DCF(P)

1.输入待下钻社区框架P

2.求得并添加节点集Vk

(1)对Vk中的每一个节点计算其到社区框架中每个社区的

距离

(2)将Vk中的每一个节点添加到距离其最近的社区

(3)形成新的社区框架P′

3.P=P′

4.如果需要进一步钻取则跳转到2继续执行，否则输出新的社区

框架P

我们将以上对社区框架进行钻取的算法2称之为DCF算法。在DCF算法中计算节点到社区的距离并添加到相应社区的时间复杂度为O(n)。当向社区框架中加入所有节点的时候，便取得了一个对整个社交网络的社区划分。对此社区结构划分的好坏可以通过Q函数来进行评价。

通过使用MCF算法挖掘出社交网络的社区框架，我们能够在不对整个社交网络进行社区划分的情况下获得其社区概况，这样使计算量大为减小。即使用户想得到更加详细的社区信息，我们也可以使用DCF算法对已有的社区框架进行可控钻取获得，从而使用户可以从不同层次对社区结构进行考察，最终我们能够实现社交网络的社区划分。下面将通过实验验证该方法的有效性。

3实验结果与分析

3.1实验数据

实验使用的数据集是netscinece合作网络[5]，由Newman于2006年统计得出，该网络描述了来自不同领域的科学家之间的合作关系。其中包含了1589个节点和2742条边，如图2所示，图中间的黑点部分是由大量的离散点聚集形成。由Newman提出的具有开创性意义的GN社区挖掘策略具有较高的社区挖掘精度，并且得到了相关学者的广泛认可和应用，所以文中将选用其作为相应的实验对比算法。

我们首先考察生成社区框架(MCF算法)和实现下钻(DCF算法)所需时间与GN算法所需时间的对比情况，分析通过社区框架下钻实现的社区划分在划分效果上与GN算法的对比情况。然后考察社区框架能否反映出完整社交网络的社区概况。

图2　netscience合作网络[5]

3.2实验结果

图3展示了在netsicence社交网络中节点的度分布。首先，该社交网络中度数为3的节点数量最多，其实际意义是与三个人有过合作的学者最多。其次，该社交网络含有少量的度数比较高的节点，这些节点代表了发表论文比较多且有较高影响力的学者。从图中的曲线走势我们可以得出该网络的节点度分布基本符合幂律分布的特性。

图3　netscience节点度分布

在MCF算法中，我们按0.2的比率提取关键子网络G′(V,E)，并对其进行社区划分。得到的关键子网络含有359个节点(占总节点个数的22.59%)，1171条边(占总边数的42.71%)，对其使用GN算法进行社区划分得到了7个大的社区以及大量的小的社区，共49个社区，如图4所示。随后在该社区框架基础之上通过使用DCF算法依次添加V4、V3、V2、V1实现了对整个社交网络的社区划分。

图4　netscience社区框架

表1给出了MCF算法、DCF算法以及使用GN算法直接对整个社交网络进行社区划分所需时间的对比情况。通过表1能够发现社区框架的挖掘所需时间仅为GN算法所需时间的28.1%，对社区框架进行下钻所需时间为GN算法的34%，总的时间比GN减少40%。

表1　运行时间对比

表2展示了通过下钻所得社区结构与使用GN算法所得社区结构质量在Q函数上的体现情况。观察可得GN算法所得到的社区结构在质量方面要略好于通过下钻所得到的社区，但是两者差距并不是很明显。

表2　社区质量对比

综合表1和表2，本文提出的算法可以在较少的时间上挖掘出一个社交网络的社区框架，并能够通过钻取社区框架实现对整个网络的社区划分，而且，社区结构质量接近GN算法所得到的社区结构质量。

下面的实验通过对比社区结构与社区框架的相关数据，验证了所得到的社区框架能够反映整个网络的社区概况。实验数据中的社区框架由MCF算获得，社区结构由DCF对社区框架挖掘获得。其编号由程序产生。

图5展示了社区结构与社区框架中对应社区的成员数目的对比情况，从图中可以看出社区框架中社区的相对大小能够反映社区结构相应社区的相对大小。例如，社区框架中编号为3、12、46、49的社区是相对较大的社区，而其对应社区结构中的社区也是相应的大社区。

图5　社区内节点个数对比

图6展示了社区结构与社区框架的社区内部边密度对比情况。所谓的社区内部边密度指的是社区内部边的条数与社区内部点的个数的商，其在netscience中的现实意义是：在社区内部成员之间的合作密切程度，边密度越大说明社区成员之间的合作越密切。通过观察发现图中两条曲线基本吻合的，但是也出现了很多不一致的情况，如社区21-28，这种不吻合主要是由社区规模太小，在统计上不准确造成的，通过观察图5可以发现社区21-28这几个社区的规模都非常的小。

图6　社区内部边密度对比

图7展示了49号社区与其他社区之间的联系情况，这里仅列出了与之有联系的社区的编号。通过观察社区结构所对应的曲线可知，社区49与社区2、22、43、48之间存在联系，其中与社区48的联系最为紧密。我们观察社区框架同样能够得到类似的信息，在社区框架中社区49与22、43、48之间存在联系，其中与社区48联系最为紧密。

图7　社区之间边的条数对比

以上实验验证了社区框架能够反映社交网络的社区结构的概况，包括社区内部节点的相对多少、社区内部边的密度、社区之间的联系紧密程度。

4结语

通过使用MCF算法，我们能够快速地在不对整个社交网络进行社区挖掘的情况下了解社区的概况，并能够使用DCF算法对社区框架进行钻取，最终实现对社交网络的社区划分。最后通过实验验证了我们所提方案的有效性。然而，我们最终实现的社区划分效果相对于成熟的GN算法来说还有待提高，同时我们也发现，本文所提方案只有应用于符合幂律分布的社交网络时，才会体现出其性能优势。今后的主要工作是当社交网络是以加权有向图表示时，如何可控的快速的发现其社区结构，同时如何利用社交网络进行高效地广告分发和流行病控制也是我们感兴趣的一个研究方向。

参考文献

[1] Burt R S,Kilduff M.Social network analysis:Foundations and frontiers on advantage[J].Annual review of psychology,2013,64(2):527-547.

[2] Fortunato S.Community detection in graphs[J].Physics Reports,2010,486(3):75-174.

[3] 窦炳琳,李澍淞,张世永.基于结构的社会网络分析[J].计算机学报,2012,35(4):741-753.

[4] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[5] Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical review E,2006,74(3):036104.

[6] Opsahl T,Agneessens F,Skvoretz J.Node centrality in weighted networks:Generalizing degree and shortest paths[J].Social Networks,2010,32(3):245-251.

[7] Barabási A L,Albert R.Emergence of scaling in random networks[J].science,1999,286(5439):509-512.

[8] Newman M E J.The structure and function of complex networks[J].SIAM review,2003,45(2):167-256.

[9] 杨博,刘大有,金弟.复杂网络聚类方法[J].软件学报,2009,20(1):54-66.

[10] Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical review E,2004,69(2):026113.

收稿日期：2015-01-05。国家自然科学基金项目(61170052)。王童童，硕士生，主研领域：社交网络，数据挖掘。李盛恩，教授。王刚，硕士生。

中图分类号TP311.13

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.07.020

MINING COMMUNITY FRAMEWORK BASED ON SOCIAL NETWORKS’ NODE CENTRALITY

Wang TongtongLi Sheng’enWang Gang

(SchoolofComputerScienceandTechnology,ShandongJianzhuUniversity,Jinan250101,Shandong,China)

AbstractAs an important topological characteristic which the real complex networks commonly have, community structure has been widely and thoroughly studied in recent 10 years. To solve the problems of community mining strategy that its time complexity is too high and lacks the interaction with users, etc., we discussed the node centrality, node’s power-law degree distribution and other characteristics of social networks, and proposed the concepts of "critical sub-network" and "community framework". Moreover, we designed the community framework mining (CFM) algorithm and the community framework drilling (CFD) algorithm. Among them, the CFM algorithm is used to mine the community framework of social networks, and CFD is used for drilling the community framework and to demonstrate the community structure from different granularities. Experimental results and analysis showed that, in a relatively short time the CFM algorithm could be used to mine out the community framework reflecting the complex networks community state, while the CFD algorithm could implement high-quality community partition in the way of user interaction.

KeywordsSocial networksCommunity structureNode centralityCommunity frameworkCommunity quality