社区发现

Community Discovery社区发现1. 社区发现简介•社区，从直观上来看，是指网络中的一些密集群体，每个社区内部的结点间的联系相对紧密，但是各个社区之间的连接相对来说却比较稀疏（图1，当然社区的定义不止有这一种）。

这样的社区现象被研究已经很多年了，最早期的记录甚至来自于80年前。

社区研究案例•比较经典的社区研究案例包括对空手道俱乐部(karate club),科学家合作网络(Collaboration network) 和斑马群体(zebras) 的社交行为研究等（见图2），其中著名的空手道俱乐部社区已经成为通常检验社区发现算法效果的标准(benchmark)之一。

社区发现•随着互联网和在线社交网站的兴起，在Twitter,Facebook，Flickr这样的用户生成内容（UCG）网站上使用社区发现的技术已经成为热潮。

在这些社区中用户相互的交流与反馈，能为传统的社区带来丰富的内容信息和新的结构，从而使社区发现有了新的发展。

社区发现算法介绍2.1 图分割•社区可以看做密集子图结构，使用图分割算法来解决。

图分割问题的目标是把图中的节点分成g个预定大小的群组，这些群组之间的边数目最小，这个问题是NP-hard 的。

2.1.1 二分图•早期的分割都是二分图，社区发现也是基于二分的，遇到多分的情况就把其中一个子图再分割。

比较经典的有谱二分法，利用拉普拉斯矩阵的第二小特征值λ2对社区二分类，这其实是属于谱方法的一种特例。

2.1.2 KL算法•KL算法通过基于贪婪优化的启发式过程把网络分解为2个规模已知的社区。

该算法为网络的划分引入一个增益函数，定义为两个社区内部的边数与两个社区边数之间的差，寻求Q的最大划分办法。

2.1.3 最大流算法•基于最大流的算法是G.W.Flake提出的。

他给网络加了虚拟源节点s和终点节点t，并证明了经过最大流算法之后，包含源点s的社区恰好满足社区内节点链接比与社区外的链接要多的性质。

•2.2 聚类•社区发现也可以看做一组内容相似的物体集合，适用于聚类算法，只要定义了节点相似度（比如说根据邻接关系定义）：•dij=∑k≠i,j(Aik-Ajk)2-------------√•其中A为邻接矩阵，i和j的邻居越多，节点相似度越高。

聚类算法和网络发现（聚类相关的）算法可以很容易地互相转化，所以两者之间的区别在理论上不是很重要。

区别在于，社区发现可以是局部的，而聚类是全网络的。

2.2.1 层次聚类•层次聚类假设社区是存在层次结构的（其实不一定，可能是中心结构），计算网络中每一对节点的相似度。

•然后分为凝聚法和分裂法两种：•凝聚法：根据相似度从强到弱连接相应节点对，形成树状图（Dendrogram），根据需求对树状图进行横切，获得社区结构。

•分裂法：找出相互关联最弱的节点，并删除他们之间的边，通过这样的反复操作将网络划分为越来越小的组件，连通的网络构成社区。

2.2.2 划分聚类/扁平聚类•像k-means什么的就很好，但是需要注意一点，k-means 需要欧氏空间，上面根据邻接关系定义的节点相似度并不适用。

2.2.3 谱聚类•图分割中的如 Ratio Cut和Normalized Cut其实和谱聚类是等价的，所以谱聚类也能用在社区发现上。

2.3 分裂法•这里的分裂法和层次聚类中的类似，区别是前者不计算节点相似度，而是删除是两个社区之间的关联边，这些边上的两点的相似度不一定很低。

其中最著名的算法就是Girvan-Newman算法，根据以下假设：社区之间所存在的少数几个连接应该是社区间通信的瓶颈，是社区间通信时通信流量的必经之路。

如果我们考虑网络中某种形式的通信并且寻找到具有最高通信流量（比如最小路径条数）的边，该边就应该是连接不同社区的通道。

Girvan-Newman算法就是这样，迭代删除边介数（EdgeBetweenness）最大的边。

2.4 谱方法•基于谱分析的社区算法基于如下事实，在同一个社区内的节点，它在拉普拉斯矩阵中的特征向量近似。

将节点对应的矩阵特征向量（与特征值和特征向量有关的都叫谱）看成空间坐标，将网络节点映射到多维向量空间去，然后就可以运用传统的聚类算法将它们聚集成社团。

这种方法不可避免的要计算矩阵的特征值，开销很大，但是因为能直接使用很多传统的向量聚类的成果，灵活性很高。

2.5 基于模块度的方法•模块度不仅仅作为优化的目标函数提出，它也是目前是最流行的用来衡量社区结果好坏的标准之一（它的提出被称作社区发现研究历史上的里程碑)。

我们知道，社区是节点有意识地紧密联系所造成的，它内部边的紧密程度总比一个随机的网络图来的紧密一些，模块度的定义就是基于此，它表示所有被划分到同一个社区的边所占的比例，再减除掉完全随机情况时被划分到同一个社区的边所占的比例：•Q=∑c=1K[A(Vi,Vi)m-(degree(Vi)2m)2]•其中Vi是第i个社区，m是整个图中边的数目。

模块度的一个优点是好坏与社区中点的数目无关。

模块度真是个好东西，第一次对社区这个模糊的概念提出了量化的衡量标准（不过据说对于小粒度的不太准）。

所以对模块度的算法优化多种多样，从贪心到模拟退火等应有尽有。

2.6 动态算法•自旋模型和同步算法应该是物理学家提出来的算法，话说物理学家在社区发现领域十分活跃，发了不少论文。

随机游走是基于以下思想：如果存在很强的社区结构，那么随机游走器（random walker)会在社区内部停留更长的时间，因为社区内部的边密度比较高。

2.7 基于统计推断的算法•基于统计推断的方法包括观察到的数据集和对模型的假设。

如果数据集是图，模型假设对节点之间如何联系的描述就要符合真实的图结构。

2.8 其他•个人觉得重叠和动态社区都很难成为一个类别，因为具体算法各有不同，用共同点“重叠”或“动态”来作为一类又太广泛了，比较适合作为特征或维度来描述。

•而Web社区特指Web页面相互连接而成的集合,这又是一个大类，底下有不少算法。

3. 社区发现算法特征•下面我从不同的角度来描绘社区发现算法的一些特征，这些特征可以用来对社区发现算法进行分类：3.1 优化目标•有一些社区发现算法比如谱方法，KL算法，以及基于最大流的社区发现方法等，给出明确的的目标函数，并提出算法来最优化目标函数。

•常用的优化目标函数有：3.1.1 Normailized Cut和conductance •如果我们将图划分为S和S¯=V-S两个部分，那么S与图中的剩下部分联系越少，说明S越独立，越有可能是一个内部紧密的社区。

我们用cut(S)来表示两者之间的联系数目：cut(S)=∑i∈S,j∈S¯A(i,j)•为了避免孤立节点的产生，我们分别除以它的权值（内部度数之和），来达到相对平均一些的分割。

这就是Normailized Cut:•Ncut(S)=∑i∈S,j∈S¯A(i,j)∑i∈Sdegree(i)+∑i∈S,j∈S¯A(i,j)∑j∈S¯degree(j)•连通度(conductance)也是类似的定义:•Conductance(S)=∑i∈S,j∈S¯A(i,j)min(∑i∈Sdegree(i),∑j∈S¯degree(j))•当涉及到多个划分V1,…,Vk时，Normalilized Cut和连通度就是它们之和。

3.1.2 Kernighan-Lin object•KL目标函数旨在使两个相同大小的社区之间的边联系最小：•KLObj(V1,…,Vk)=∑i≠jA(Vi,Vj)•其中A(Vi,Vj)=∑u∈Vi,v∈VjA(u,v),|V1|=|V2|=…=|Vk|。

3.2 粒度控制（社区数目可不可控）•对于有层次的社区发现算法来说的，比如某些二分社区算法，是通过不断递归的划分子社区来获得预定的社区数目。

而某些算法，像层次聚类和MCL，基于概率模型的社区发现算法等，允许用户通过调节参数来间接控制输出社区的数目。

•另一些算法，像模块度优化算法，它的社区数目是由优化函数决定的，不需要用户来设定社区的数目。

3.3 规模•很多算法在设计的时候，并没有特别地考虑伸缩性，在面对整个Web以及大型社交网络时动辄百万甚至千万个点时效果不佳。

比如GN算法，需要计算即通过每条边的最短路径数目（edge betweeness)，复杂度相当高，像谱聚类算法，能处理10K个点和70M条边就不错了。

•所以，有些算法比如Shingling算法等，使用的方法相对简单，从而能适合大规模的社区发现的运行要求。

3.4 局部社区发现•所谓的局部社区发现，是指只根据临近的邻居节点发现社区结构，而不考虑全局的网络，这与全局社区发现中对图中的每一个节点都打上社区标签的做法相对应。

•在整个网络图很大，数据集不能全部加载到内存时，使用局部社区发现可以只加载图的一部分，发现一个局部社区，然后迭代地调用该方法来逐一地提取社区结构。

3.5 重叠社区•很多社区发现算法，比如图分割算法，将整个网络划分为多个独立的社区结构。

但是在现实中，许多网络并不存在绝对的彼此独立的社团结构，相反，它们是由许多彼此重叠互相关联的社团构成，比如说在社交网络中，一个人根据兴趣的不同，有可能属于多个不同的小组等。

所以，很多类似派系过滤算法（CPM）这样旨在发现重叠社区的算法也被不断地提出来。

3.6 评价标准•社区发现算法常用的评价标准有：准确率，召回率，F1值•一个大规模数据集合中检索文档的时，可把文档分成四组：系统检索到的相关文档（A），系统检索到的不相关文档（B），相关但是系统没有检索到的文档（C），不相关且没有被系统检索到的文档（D）：•准确度定义为：pr=AA+C•召回率定义为：rc=AA+B•F-measure是准确率和召回率协调之后的结果，定义为：•PWF=2×pr×rcpr+rc•同理，社区也可以用这个概念。

平均聚类纯度•平均聚类纯度，average cluster purity。

假设算法发现了C={C1,…,CK}个社区，我们假设社区Ci有ni个点，每个点分别为{v1,i,…,vni,i}。

令Ml,i为点vl,i 真实归属的标签，平均聚类纯度为定义为•ACP=1k∑i=1k∑l=1niδ(domi∈Ml,i)ni•即社区Ci中主要标签的点占社区所有点的数目比例。

4. 社区发现的趋势• 4.1 动态社区发现 (Dynamic Networks)•很多社区算法都把社区看做静态的图，但是事实上的社交网络是随着时间逐渐演变的。

这些社区如何形成和消解，它们的的动态变化该如何处理，确实是一个研究热点。

• 4.2 异构网络上的社区发现(Heterogeneous Network)•日常算法中我们都假定网络中的点和边属于同一类型。