美文网首页
[ML]Community Detection社群发现算法-文献

[ML]Community Detection社群发现算法-文献

作者: pingpong_龘 | 来源:发表于2019-07-06 22:44 被阅读0次

1. 背景

项目组要做社交网络的拓展，借机研究学习了社群发现的一些基本概念和常见算法。目前该领域没有一个算法属于绝对一枝独秀的，所以从不同的维度也出现了不同的算法，但基本转向为以模块度Q为损失函数的优化方案。
这了简单整理了论文中常见的社群发现的算法。

2. Community Detection

2.1 Modularity Q

模块度（Modularity）用来衡量一个社区的划分是不是相对比较好的结果。一个相对好的结果在社区内部的节点相似度较高，而在社区外部节点的相似度较低。

模块度的大小定义为社区内部的总边数和网络中总边数的比例减去一个期望值，该期望值是将网络设定为随机网络时同样的社区分配所形成的社区内部的总边数和网络中总边数的比例的大小，于是模块度Q为：
Q = \frac{1}{2m}\sum_{ij}[A_{ij} - \frac{k_ik_j}{2m}]\delta(C_i,C_j)

社区内部的边数和网络中总边数的比例：

\frac{\sum_{ij}A_{ij}\delta(C_i,C_j)}{\sum_{ij}A_{ij}} = \frac{1}{2m}\sum_{ij}A_{ij} \delta(C_i,C_j)

  • A_{ij}为网络的邻接矩阵的一个元素，(如果i和j相连，则A=1,否则A=0)
  • C_i$$C_j分别表示点i和j所在的两个社区,
  • m为网络中的总边数。
  • 函数\delta(C_i,C_j)如果i和j在同一个社区（即：C_i = C_j）,则为1，否则为0
  • k_i表示点i的度: k_i = \sum_{w} A_{iw}

Modularity(模块度), 这个概念是2003年一个叫Newman的人提出的。这个人先后发表了很多关于社区划分的论文，包括2002年发表的著名的Girvan-Newman(G-N)算法，和2004发表的Fast Newman(F-B)算法，Modularity就是F-B算法中提出的（03年提出的概念，04年确认发表）。
  在2006年的时候Newman重新定义了Modularity，实际上只是对原来的公式做了变换，使其适用于Spectral Optimization Algorithms。
  早期的算法不能够很好的确认什么样的社区划分是最优的。Modularity这个概念就是为了定义一个对于社区划分结果优劣的评判。

https://blog.csdn.net/marywbrown/article/details/62059231

在进行每次划分的时候计算Q值，Q取值最大的时候则是此网路较理想的划分。Q值的范围在0-1之间，Q值越大说明网络划分的社区结构准确度越高，在实际的网络分析中，Q值的最高点一般出现在0.3-0.7之间。

2.2 模块密度

Newman等人在文献中提出了模块度Q作为网络社区划分质量的评价参数，其公式定义为：
D_\lambda = \sum_{i=1}^{m} \frac{2\lambda L(V_i,V_j) - 2(1-\lambda)L(V_i-\bar{V_i})}{|V_i|}

在公式中， eii是边所连接的两个节点均在社区Gi内的边占网络中所有边的比例，ai是边所连接的节点中至少有一个在社区Gi内的边占网络中所有边的比例。模块度函数可以反映社区结构的明显程度，社区结构越明显，则模块度函数值越大，反之社区结构越弱，模块度函数值越小。
使用模块度作为社团划分的评价参数存在着对于小社团结构无法正确发现的分辨率极限问题，所以目前也有很多对于模块度进行改进的研究。Fortunato等人在文献[9]中提出了使用模块密度作为社区划分的评价函数，其定义为：
其中L（Vi， Vi）表示某个社团内部的连接数量，而表示该社团与其他社团的连接数量，基于复杂网络的邻接矩阵A，它们分别可以表示为：
模块密度定义了所有子图平均内部连接率和所有子图与子图之间的平均外部连接率的差，反映了模块内部和模块之间的连接紧密程度。对于网络中的社团结构，其基础定义就是社团内部连接较为紧密而不同社团之间的连接较为稀疏

3. 复杂网络社群发现方法

3.1 传统社群发现算法

3.1.1 图分割

3.1.1.1 Kernighan & Lin algorithm - K-L算法

K-L（Kernighan-Lin）算法是一种将已知网络划分为已知大小的两个社区的二分方法，它是一种贪婪算法。它的主要思想是为网络划分定义了一个函数增益Q，Q表示的是社区内部的边数与社区之间的边数之差，根据这个方法找出使增益函数Q的值成为最大值的划分社区的方法。

具体策略是，将社区结构中的结点移动到其他的社区结构中或者交换不同社区结构中的结点。从初始解开始搜索，直到从当前的解出发找不到更优的候选解，然后停止。

K-L算法必须预先指定2个社区的大小，否则会得到错误的结果。这使得K-L算法无法应用于大多数真实网络。即使K-L算法的这一缺点得以克服，作为图分割方法，其先天性不足仍然难以解决。K-L算法在稀疏图中的时间复杂度是O(n^3)。

原始论文：
An efficient heuristic procedure for partitioning graphs. Kernighan, Brian W., and Shen Lin (1970)

WIKI:
Kernighan–Lin_algorithm

博客：
Kernighan-Lin算法，2017
Lin-Kernighan启发式算法的具体过程及思想是什么？

3.1.1.2 Spectral Bisection method 谱二分法

早期的分割都是二分图，社区发现也是基于二分的，遇到多分的情况就把其中一个子图再分割。比较经典的有谱二分法，利用拉普拉斯矩阵的第二小特征值λ_2
对社区二分类，这其实是属于谱方法的一种特例。谱二分法的步骤如下：

  • 对于网络的相似度矩阵W=[wi,j]，计算对角矩阵 Di,i=∑jNwi,j，其中wi,j
  • 计算拉普拉斯（Laplacian）矩阵 L=D−W

该拉普拉斯矩阵必有一个特征值为0，且对应的特征向量为1⃗ =[1,1,⋯,1]^T。而不为零的特征值所对应的特征向量的各元素中，同一个社区内的节点对应的元素是近似相等的。可以征明，除零特征值外，其它特 征值均大于零。谱二分法即是根据L的第二个小特征值λ_2：将网络分为两个社区。λ_2被称为图的代数连接度，如果其值越小，谱二分法的效果就越好。谱二分法的主要缺点是只能将图分成2个子图，或者说偶数个子图。这使得人们在使用这种方法时，预先不能确定究竟将图分成多少个子图才合适

原始论文：
An algorithm for partitioning the nodes of a graph.Barnes, Earl R (1982)

3.1.1.3 Maximum flows 最大流算法

基于最大流的算法是G.W.Flake提出的。他给网络加了虚拟源节点ss和终点节点tt，并证明了经过最大流算法之后，包含源点ss的社区恰好满足社区内节点链接比与社区外的链接要多的性质。

原始论文：
Efficient identification of web communities.Flake, Gary William, Steve Lawrence, and C. Lee Giles. ACM, 2000.
Self-organization and identification of web communities.Flake, Gary William, et al, (2002)

3.1.1.4 Level-structure partitioning 多层次图分割

Graph partitioning algorithms with applications to scientific computing.Pothen, Alex, 1997

3.1.2 聚类

当社区的边非常密集，数目远大于点时，图分割可能就不太好使了，这时候社区发现可能更接近于聚类。我们把社区发现看做一组内容相似的物体集合，使用聚类算法。和图中的社区发现相比，图中的社区点与点之间可以用边来表示联系的紧密，而聚类中的社区，需要定义点之间的相似度，比如说根据邻接关系定义：
//TODO:
dij=∑k≠i,j(aik−ajk)2‾‾‾‾‾‾‾‾‾‾‾‾‾√
其中A=(aij)，为邻接矩阵，i和j的邻居越多，节点相似度越高。 聚类算法和网络发现（聚类相关的）算法可以很容易地互相转化。另外，社区发现可以是局部的，而聚类是全网络的

3.1.2.1 Hierarchical clustering 层次聚类

层次聚类假设社区是存在层次结构的（其实不一定额，可能是中心结构），计算网络中每一对节点的相似度。 然后分为凝聚法和分裂法两种:

  • 凝聚法（Agglomerative algorithms）：根据相似度从强到弱连接相应节点对，形成树状图（Dendrogram），根据需求对树状图进行横切，获得社区结构。凝聚法的缺陷在于在某些应用中，当社区数目已经知道时，未必能得到正确的社区结构。另外，凝聚算法倾向于发现社区的核心，而忽略社区的外围。社区的核心部分往往与它周围点联系密切，因而易于发现．两社区的蒯边部分由于相对来说联系较少，所以很难划分。在一些情况下，某个点仅仅和特定的社区有一条边，凝聚算法很难正确划分该点。
  • 分裂法（Divisive algorithms）：找出相互关联最弱的节点，并删除他们之间的边，通过这样的反复操作将网络划分为越来越小的组件，连通的网络构成社区

原始论文：
Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning. Vol. 1. Springer, Berlin: Springer series in statistics, 2001.

3.1.2.2 Partitional clustering 划分聚类

基于划分的方法（Partition-based methods）：其原理简单来说就是，想象你有一堆散点需要聚类，想要的聚类效果就是“类内的点都足够近，类间的点都足够远”。首先你要确定这堆散点最后聚成几类，然后挑选几个点作为初始中心点，再然后依据预先定好的启发式算法（heuristicalgorithms）给数据点做迭代重置（iterativerelocation），直到最后到达“类内的点都足够近，类间的点都足够远”的目标效果。

Partition-based methods聚类多适用于中等体量的数据集，但我们也不知道“中等”到底有多“中”，所以不妨理解成，数据集越大，越有可能陷入局部最小。

其实从某种角度讲，划分聚类是完全不用赘述的一种聚类方法，可能也是最常见的聚类算法了。著名的k-means算法就是个中典型。这次的内容主要是通过k-means聚类算法来总体介绍一下划分聚类。

简单来讲，k均值聚类究竟做了什么事，我们可以这样来看，有N个数据点的集合D={x1,x2,…,xn}，每个x_i代表一个特征向量，目标是将这N个点根据某种相似准则将其划分到K个分类中。而k均值所表达的重要在于相似准则的选取，即不断的使用类簇的均值来完成这样的划分。当然也有书把这种相似准则称之为评分函数。基于划分的聚类算法对于homogeneity的实现是通过选取适当的评分函数并使每一个数据点到它所属的聚类中心的距离最小化。而关键就是如何定义这种距离，和所谓的聚类中心。举个例子来讲，如果定义聚类间距离为欧式距离，那么可以使用协方差的概念来定义通用的评分函数。划分聚类的思想是最直观和易懂的分类思想，因此我也不在这里长篇介绍，还是以算法的实现和代码来直观表现划分聚类的性能。

原始论文：
MacQueen, James. “Some methods for classification and analysis of multivariate observations.” Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. Vol. 1. No. 14. 1967.

博客：
聚类之层次聚类、基于划分的聚类（k-means）、基于密度的聚类、基于模型的聚类

3.1.2.3 Spectral clustering 谱聚类

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

3.1.3 Divisive algorithms 分裂方法

这里的分裂法和层次聚类中的类似，区别是前者不计算节点相似度，而是删除是两个社区之间的关联边，这些边上的两点的相似度不一定很低。其中最著名的算法就是Girvan-Newman算法，根据以下假设：社区之间所存在的少数几个连接应该是社区间通信的瓶颈，是社区间通信时通信流量的必经之路。如果我们考虑网络中某种形式的通信并且寻找到具有最高通信流量（比如最小路径条数）的边，该边就应该是连接不同社区的通道。Girvan-Newman算法就是这样，迭代删除边介数（Edge Betweenness）最大的边。

  • G-N算法(Girvan & Newman)

针对加权网络的Girvan-Newman(GN)算法
这样的社区发现算法的主要思路为：计算网络中所有边的边介数，然后寻找边介数值最大的边并移除。在移除时，会改变一些边的边介数。以前经过被移除边的最短路径，现在改为经由其他边，因此必须重新计算边介数，然后再次搜索值最大的边并移除，依此类推。当一条接一条边被移除时，最初连通的网络最终会被分成两部分、三部分等等，直至网络的每一个成为一个社区，是一种分裂算法。

算法的执行过程可用树状图表示，如下图所示。算法从顶部开始生成树状图，首先是单个连通网络，然后将其不断划分，直至每个分支只有单个结点为止。在算法运行期间，每个独立的网络结构状态对应于树状图的水平切分，在图2中用红线表示。与红线相交的每个分支代表一组节点，即一个社区，沿分支向下到底部的全部节点都为其成员。因此对于一个连通网络，树状图能够得到算法执行全过程中每个阶段里网络划分的社区结构。

原始论文：

Girvan, Michelle, and Mark EJ Newman. “Community structure in social and biological networks.” Proceedings of the national academy of sciences 99.12 (2002): 7821-7826.

3.2 基于模块度优化的算法

3.2.1 贪心策略

3.2.1.1 Fast Newman

Newman第一次提出模块度定义就是在2004年发表的这篇文章“fast algorithm for community structure in networks”，第一次用量化的公式来确定社区划分。

首先，我们来看Newman如何定义社区的：the vertices in networks are often found to cluster into tightly knit groups with a high density of within-group edges and a lower density of between -group edges。

用大白话说就是：社区内部的边尽可能地多，但是社区之间的边尽可能地少

一些定义：i、j指社区i和社区j n是网络中节点的数量； m是网络中边的数量。一条边上连接两个节点，和明显，2m即网络中所有节点度之和

如何变成算法可操作性？

意思来了，我们只要优化Q就好了，但是如何把n个节点划分多少个社区？每个社区多少个节点？作者指出有2n-1种可能，这样的话根本无法将Q推广在高于20节点以上的网络？为了减少时间复杂度，作者提出一种贪婪策略

  1. 首先将网络中每个节点自定义成一个社区
  2. 计算出两两社区结合时Q的值，找到Q增加最大的或者减少最少的合并方式进行社区合并
  3. 直到所有社区合并成一个大社区时停止，找出合并过程中最大的Q是的社区划分结果

这个时候，Newman有注意到，当两个社区合并时，模块度的增量detaQ=(eji+eij-2ai*aj)=2(eij-2ai*aj)

原始论文：
Fast algorithm for detecting community structure in networks, 2004

博客：
Fast Newman-FN算法以及模块度定义介绍

3.2.1.2 CNM

在Newman快速算法的基础上采用堆数据结构计算和更新网络的模块度，提升了计算速度。

原始论文：
Finding community structure in very large networks. (2004)

3.2.1.3 Multilevel算法(Fast-Unfolding或简称Louvain)

Louvain算法是一种基于模块度Q的社区发现算法，但很多博客或paper里相同的场景（列举基于模块度Q的贪心算法时），会使用Fast unfolding算法，
本来以为是不同的两种算法而已（因为<Network Community Detection: A Review and Visual Survey>这篇paper中提到Louvain时候的引用是2004年Clauset的一篇paper，而Fast unfolding是2008年发的一篇paper），
但是其他很多文档又是两个名字叫来叫去，分的不是很清楚，索性后来专门去查了下，
原来这两个是同一个算法：

最初一个叫Etienne Lefebvre的同学在 UCL (Université catholique de Louvain) 的硕士论文中首次提出这种算法（2007年），然后Vincent Blondel, Jean-Loup Guillaume和Renaud Lambiotte重新优化并提升了该算法，并于2008年发表了
<Fast unfolding of communities in large networks>，因为易于理解，属于非监督且计算快速，可获取层次化的社区发现结果，得以成为了社区发现(Community Detection)的State Of The Art。
而因为三位作者在发表的该算法的时候都在Louvain大学，所以后面该算法简称为Louvain。

所以说<Network Community Detection: A Review and Visual Survey>这篇paper有bug...

该算法优点如下：
（1）计算速度很快，可用于大规模网络。
（2）是一种自下而上的凝聚过程，不会出现对小规模社团的探测遗漏现象，即解决了分辨率问题。（3）可应用于大规模的加权网络。 然而，在实际情况下，在顶点的直接邻近内的封闭社区可能是不准确的并且产生虚假伪分区。 因此，不清楚某些中间分区是否可以对应于图的有意义的分层级别。 此外，算法的结果取决于在顶点上的顺序扫描的顺序。

原始论文：

Blondel, Vincent D., et al. “Fast unfolding of communities in large networks.” Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008.

3.2.2 Simulated Annealing 模拟退火

模拟退火算法（Simulate Annealing Arithmetic，SAA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法。

模拟退火算法是S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi等人在1983年发明的，1985年，V.Černý也独立发明了此演算法。模拟退火算法是解决TSP问题的有效方法之一。

3.2.3 Extremal optimization 极值优化

EO算法是受复杂系统自组织临界进化模型的启发，发展形成的一种启发式只能算法。自然界和人类社会中存在许多复杂系统,它们在无外界驱动的情况下,能够自发地演化形成复杂的结构,这样的结构能以一种精妙的方式优化资源的使用.例如生态系统进化形成了一种强大相互依赖连接的网络, 能高效地使用有限的资源;网络系统如果工作在临界状态下,就能获得最高的数据传输效率.为了描述这种突现的复杂性,Bak提出了自组织临界(SOC)的概念.

Duch于2005年使用EO算法用于模块度优化问题:
Community detection in complex networks using Extremal Optimization

3.2.4 Spectral optimization 谱优化

3.3 动态算法

自旋模型和同步算法应该是物理学家提出来的算法，话说物理学家在社区发现领域十分活跃，发了不少论文。随机游走是基于以下思想：如果存在很强的社区结构，那么随机游走器（random walker)会在社区内部停留更长的时间，因为社区内部的边密度比较高。
源自：http://www.shesong.org/2017/02/22/复杂网络调研/

  • 自旋模型
  • 随机游走
  • 同步算法
  • Diffusion 扩展社区

重点介绍一下随机游走：

  • Label Propagation
    标签传播算法是基于图的半监督学习方法，基本思路是从已标记的节点的标签信息来预测未标记的节点的标签信息，利用样本间的关系，建立完全图模型。
    每个节点标签按相似度传播给相邻节点，在节点传播的每一步，每个节点根据相邻节点的标签来更新自己的标签，与该节点相似度越大，其相邻节点对其标注的影响权值越大，相似节点的标签越趋于一致，其标签就越容易传播。在标签传播过程中，保持已标记的数据的标签不变，使其将标签传给未标注的数据。最终当迭代结束时，相似节点的概率分布趋于相似，可以划分到一类中。
  • Infomap
    在具体做法上，为了区分随机游走从一个群组进入到了另一个群组，除了群组的名字之外，对于每个群组的跳出动作也给予了一个编码。比如，下图（c）中红色节点部分是一个群组，群组名的编码是 111，跳出编码是 0001。这样在描述某个群组内部的一段随机游走路径的时候，总是以群组名的编码开头，以跳出编码结束。

3.4 Overlapping社群的算法

社群算法的本质是分割和聚类，但以上大部分算法的前提都是每个节点或者每个用户都被划分到不同的群体中，但是如果是类似兴趣小组的划分，每个人是存在多个兴趣的，所以需要算法支持节点在多个类别中。此类相关的算法属于Overlapping社群的算法。

Palla的论文"Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society"
提出的CPM算法是第一个能发现重叠社区的算法，CPM算法就不展开讨论了，如果是研究重叠社区发现算法的话肯定是看过的。
值得一提的是Kumpula在前人基础上提出的SCP算法(Sequential Algorithm for Fast Clique Percolation)较大的提升了团渗透算法的速度。该类算法的问题这篇文章虽然也是简单的一说，但是比之前某些人简单的用一个K值不好确定来敷衍了事要来的有意义的多：基于团渗透思想的算法需要以团为基本单元来发现重叠，这对于很多真实网络尤其是稀疏网络而言，限制条件过于严格，只能发现少量的重叠社团(Identification of Functional Modules in a PPI Network By Clique Percolation Clustering)。

来源：https://blog.csdn.net/loptimistic/article/details/8173555

4. 博客 / 文档

  1. Community detection in graphs,Santo Fortunato,2010
    这个领域近十年来的总结，很牛的综述！是最近看过的所有文档里最全面的一个。
    优点是：目前没看到过比这篇更全面的文章
    缺点是：这篇文章是2009年写的，2010年发的，所有都是些经典算法，不会有这几年新出的各种算法。
    The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.
  1. 复杂网络调研,2017,shesong
    目前看下来，纯博客中，写的最全面的一篇，包括每个算法背后的paper和文献引用都做的很详细，本篇文章也基本参照这篇文章的结构来梳理的，唯一就是有些谱优化的算法，没有详细的解释和论文说明。

  1. 社团发现算法综述, 南海有鹏
    基于原始论文：复杂网络社团发现算法研究新进展,国防科技大,2011

    近期想对社区发现领域进行一下简单研究，看到一篇不错的文章，文章是根据国防科大骆志刚教授的论文《复杂网络社团发现算法研究新进展》整理的，主要是对社区发现的一些算法进行简单分析。

    • 基于模块度优化的社团发现算法
      也就是优化模块度Q值的一部分算法。在此基础上，本文又划分了三个类别：
      • 采用聚合思想，
        也就是分层聚类中的自底向上的作法。典型算法有Newman快速算法(FN算法)、CNM算法(Finding Local Community Structure in Networks)和MSG-MV算法(Multistep Greedy Algorithm Identifies Community Structure in Real-World and Computer-Generated Networks)等。
      • 采用分裂思想
        也就是分层聚类中自顶向下的方法。代表当然就是Newman的GN算法，但是GN的复杂度实在是高了些，所以Newman之后提出的一种谱方法(Modularity and Community Structure in Networks)，吐槽一句Newman真的是这方面的大牛啊。。。再吐槽一句，Newman那本800多大洋的书真是想买但真是贵啊！
      • 直接寻优法
        这类算法的两个代表EO算法(Community Detection in Complex Networks Using External optimization)和整数规划方法我还都没有看过，但是一些基于遗传算法和蚁群的智能划分方法也属于此类。但是在2007年的论文"Resolution Limit in Community"中认为基于Q值的优化方法无法处理粒度小于一定程度的网络，虽然后续跟进了一些优化的算法，但是此类方法在处理真实网络时还是很难反映真实的社团结构。
    • 基于谱分析的社团发现算法
      这类算法的普遍方法是将节点对应的矩阵特征分量看成空间坐标，将网络节点映射到多维向量空间去，运用传统的聚类算法将它们聚集成社团。这种方法不可避免的要计算矩阵的特征值，开销很大，但是因为能直接使用很多传统的向量聚类的成果，灵活性很高。
    • 基于信息论的社团发现算法
      Rosvall的两篇论文，"An Information-theoretic Framework for Resolving Community Structure in Complex Networks"和"Maps of Random Walks on Complex Networks Reveal Community Structure"分别运用了模拟退火优化算法和随机游走的有效编码方式。09年的论文"Community Detection Algorithms:A Comparative Analysis"已经测试表明该方法是目前非重叠社团发现算法中准确度最高的。
    • 基于标号传播的社团发现算法
      Raghavan基于网络的边很多时候代表信息的传播这一思想提出的LPA算法(Near Linear Time Algorithmto Detect Community Structures in Large-scale Networks)。LPA算法首先为每个节点指派唯一标号， 在每一步迭代中, 每个节点将自身标号更新为其邻节点出现次数最多的标号，如果存在多个相同的最多标号， 则随机选择一个作为更新值，若干次迭代后密集相连的节点会收敛于同一标号，最终，具有相同标号的节点归为一个社团。该算法时间复杂度为O(m)，收敛速度非常快。"Towards Rea-l time Community Detection in LargeNetworks"中改进了标号更新规则，进一步降低了计算开销。
  1. awesome-community-detection论文合集github
    近几年的社区发现领域的论文集和，包括因子分解，深度学习，标签传播等多个领域的论文。(比较多的是16年到19年的论文)
  1. 社交网络中的传播——来自随机实验的证据
  1. 金融风控反欺诈之图算法
    张行军，Abakus 高级风控算法经理。曾先后工作于百度、360 等公司。
    先介绍了金融借贷业务流程：用户前来申请借贷，会先经过欺诈识别，把欺诈团伙和主观欺诈的个人拒绝掉，然后对通过的人做信用评估，最后根据额度模型，算出利润最大化时放款金额。
    本文主要分享这两类的主要算法
  • 基于模块度的louvain
    每次把节点分配到邻居节点之后，计算模块度的变化，如果是模块度是最打的，那么这个节点就是在这个社区的。然后不断循环，直到收敛。
  • 基于信息熵的infomap
    1. 初始化，对每个节点都视作独立的社区；
    2. while 平均比特的值不再下降；
    3. 对图里的节点随机采样出一个序列，按顺序依次尝试将每个节点赋给邻居节点所在的社区，取平均比特下降最大时的社区赋给该节点，如果没有下降，该节点的社区不变。
  • 基于相似度的node2vec
    这个 node2vec 优化目标函数，因为它跟大名鼎鼎的 word2vec 是一样。
    我们最初是用一个 Python 写的包，跑一遍算法需要一周。后来想，既然优化目标是一样的，那能不能用 word2vec 包，因为 word2vec 用 c 写的，而且还采用了 Hierarchical Softmax，negative sampling 加速。
    然后在网上找到了一个套用 word2vec 实现的 node2vec 包，速度快很多。
  1. 复杂网络中聚类算法总结，2016
    网络，数学上称为图，最早研究始于1736年欧拉的哥尼斯堡七桥问题，但是之后关于图的研究发展缓慢，直到1936年，才有了第一本关于图论研究的著作。20世纪60年代，两位匈牙利数学家Erdos和Renyi建立了随机图理论，被公认为是在数学上开创了复杂网络理论的系统性研究。之后的40年里，人们一直讲随机图理论作为复杂网络研究的基本理论。然而，绝大多数的实际网络并不是完全随机的。1998年，Watts及其导师Strogatz在Nature上的文章《Collective Dynamics of Small-world Networks》揭示了复杂网络的小世界性质。随后，1999年，Barabasi及其博士生Albert在Science上的文章《Emergence of Scaling in Random Networks》又揭示了复杂网络的无标度性质(度分布为幂律分布)，从此开启了复杂网络研究的新纪元。
    随着研究的深入，越来越多关于复杂网络的性质被发掘出来，其中很重要的一项研究是2002年Girvan和Newman在PNAS上的一篇文章《Community structure in social and biological networks》，指出复杂网络中普遍存在着聚类特性，每一个类称之为一个社团(community)，并提出了一个发现这些社团的算法。从此，热门对复杂网络中的社团发现问题进行了大量研究，产生了大量的算法，本文试图简单整理一下复杂网络中聚类算法，希望对希望快速了解这一部分的人有所帮助。本文中所谓的社团跟通常我们将的聚类算法中类(cluster)的概念是一致的。
  1. 社团检测（community detection）相关文献整理（2015-2018）
    刚刚开始接触community detection相关的内容，在找资料和了解相关定义、算法的过程中发现自己的记录很混乱，所以借此记录下自己的一些学习过程，希望可以一起学习交流。
    首先咱们来讨论一下文献查找，本文主要列出了机器学习、数据挖掘和人工智能领域的相关文献，我是直接搜索这些领域的相关会议，然后找到accepted papers，利用关键词（community）进行文章的查找和整理，当然也可以直接在百度学术、必应学术、谷歌学术等一系列搜索引擎中或者dblp之类的数据库利用关键词查找。其实深以为自己这样的查找方式有点低效，得一篇篇地看摘要，了解讲的啥才能知道是不是自己要找的文献，但是好像也没有更加高效的方法，毕竟要自己一步一步地去做，才能更了解。（所以我也不知道自己在说啥。。。）
  1. 写社团划分综述想到的
    复杂网络的社团划分相关学习进行了好一阵子，周遭乱七八糟的事情搞得一直没有专心做总结，最近写综述才发现很多看过的东西不总结下来真心是记不住，于是，好的，整理整理吧，这次先从国防科大骆志刚教授的论文《复杂网络社团发现算法研究新进展》说起...
  1. Community Detection 算法,2013
    一个 PPT 报告:社区发现（Community Detection）算法用来发现网络中的社区结构，也可以视为一种广义的聚类算法。
  1. Community Detection – 思考：什么样的算法才有效
    注意，我特指了Social Network。例如，如果是对Youtube的video进行community detection，我认为无论是clustering的方法，还是partitioning的方法，应该都能够取得不错的效果。但是对于Social Network，情况不一样。
    Social Network一个最大的特点，是community的overlapping。绝大部分的人，它其实都属于多个community。social network上会有同事圈，还会有同学圈。而当所有的人都是处于多个community的时候，他们构成的网络就是一个非常密集，没有什么几何特性的网络。这样的large-scale social network和平时做实验用的小规模的网络是完全不一样的。很难找到一个cut能够将网络很好的分开，所以graph partitioning的方法我预测不会有太好的效果。clustering的方法亦是同理。
    另外一个问题是，无论是clustering还是graph partitioning，会将network中的每一个node都分类，每一个node一定会有一个所属的community。而在social network中，情况不是这样。有一部分人会归属于多个community的同时，还有相当一部分人可能不属于任何的community。
  1. 演化算法（EA）在社区发现方面的进展
    区（Community）结构在复杂网络中普遍存在，整个网络由许多个社区组成，同一社区内的节点与节点之间连接紧密，而社区与社区之间的连接比较稀疏。
    为了发现及分析复杂网络中的社区结构，许多社区发现（Community Detection）算法被提出。
    一般而言，复杂网络中的社区发现是一个 NP 难问题，而多数现有社区发现算法都是基于贪婪算法，因此，当面临大规模复杂网络时，这类算法的性能有时不能达到使用者的要求与期望。
    与此同时，很多社区发现算法需要关于社区结构的先验信息，而在实际社会网络中，很难获得此类信息。为此，越来越多的研究者们开始关注基于演化算法的社区发现算法。
    今天我们将与大家分享 5 篇基于演化算法的社区发现相关论文，由于笔者能力有限，因此，如果分享过程中疏漏了重要工作，还请大家不吝赐教与指正。
  1. 基于社区发现算法和图分析Neo4j解读《权力的游戏》
    几个月前，数学家 Andrew Beveridge 和Jie Shan在数学杂志上发表《权力的网络》，主要分析畅销小说《冰与火之歌》第三部《冰雨的风暴》中人物关系，其已经拍成电视剧《权力的游戏》系列。他们在论文中介绍了如何通过文本分析和实体提取构建人物关系的网络。紧接着，使用社交网络分析算法对人物关系网络分析找出最重要的角色；应用社区发现算法来找到人物聚类。
    其中的分析和可视化是用Gephi做的，Gephi是非常流行的图分析工具。但作者觉得使用Neo4j来实现更有趣。
  1. LOUVAIN——社交网络挖掘之大规模网络的社区发现算法
    Louvain算法是基于模块度（Modularity）的社区发现算法，该算法在效率和效果上都表现比较好，并且能够发现层次性的社区结构，其优化的目标是最大化整个图属性结构（社区网络）的模块度。
    i>. 每个点作为一个community，然后考虑每个community的邻居节点，合并到community，然后看delta Q；找到最大的正delta Q，合并点到community；多进行几轮，至不再变动，那么结束；
    其中存在的问题是，不同的节点访问顺序将导致不同的结果，试验中发现这个顺序对结果影响不大，但是会在一定程度上影响计算时间。
    ii>. 将新的community作为点，重复上述过程。那么如何确定新的点之前的权重呢？答案是将两个community之间相邻的点之间的权重和作为两个community退化成一个点后的新的权重。
    Spark实现： https://github.com/Sotera/spark-distributed-louvain-modularity
  1. Github：Sotera/distributed-graph-analytics
    基于scala实现的图分析框架。实现的算法包括如下几个：
    • High Betweenness Set Extraction
    • Weakly Connected Components
    • Page Rank
    • Leaf Compression
    • Louvain Modularity

相关文章

网友评论

      本文标题：[ML]Community Detection社群发现算法-文献

      本文链接：https://www.haomeiwen.com/subject/cizmhctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|[ML]Community Detection社群发现算法-文献|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！