社区要满足两个条件：一是社区的成员有共同的话题和爱好；二是社区的成员之间的联系相比和社区外的联系要紧密。
通过用户的搜索情况可以找到有相同爱好的人，这些人组成候选社区成员。比如用户搜索“NBA”，这个用户就是候选的NBA社区成员。
通过一定的算法计算这些成员间的紧密程度，大于一定阀值的成员共同组成了NBA社区。算法有HITS，类似于搜索引擎的链接分析，每个人都有一个H值和A值，迭代计算。也可以用聚类的算法，每个成员可以表示为一个向量，向量取值为1标识和另一个成员有联系，取0标识没有联系，通过聚类可以发现社区。这种方式还可以发现多个NBA社区。

1、什么是社区
如果一张图是对一片区域的描述的话，我们将这张图划分为很多个子图。当子图之内满足关联性尽可能大，而子图之间关联性尽可能低时，这样的子图我们可以称之为一个社区。
2、社区发现算法及评价标准
社区发现算法有很多，例如LPA，HANP，SLPA以及我们今天的主人公——Louvain。不同的算法划分社区的效果不尽相同。那么，如何评价这些算法孰优孰劣呢？

用模块度modularity来衡量。模块度定义如下：模块度是评估一个社区网络划分好坏的度量方法，它的物理含义是社区内节点的连边数与随机情况下的边数只差，它的取值范围是 [−1/2,1)。可以简单地理解为社区内部所有边权重和减去与社区相连的边权重和。


Louvain算法
一种基于模块度的图算法模型，与普通的基于模块度和模块度增益不同的是，该算法速度很快，而且对一些点多边少的图，进行聚类效果特别明显。

算法流程：

1、初始时将每个顶点当作一个社区，社区个数与顶点个数相同。

2、依次将每个顶点与之相邻顶点合并在一起，计算它们的模块度增益是否大于0，如果大于0，就将该结点放入该相邻结点所在社区。

3、迭代第二步，直至算法稳定，即所有顶点所属社区不再变化。

4、将各个社区所有节点压缩成为一个结点，社区内点的权重转化为新结点环的权重，社区间权重转化为新结点边的权重。

5、重复步骤1-3，直至算法稳定。
# coding=utf-8
import collections
import random

def load_graph(path):
    G = collections.defaultdict(dict)
    with open(path) as text:
        for line in text:
            vertices = line.strip().split()
            v_i = int(vertices[0])
            v_j = int(vertices[1])
            w = float(vertices[2])
            G[v_i][v_j] = w
            G[v_j][v_i] = w
    return G

class Vertex():
    def __init__(self, vid, cid, nodes, k_in=0):
        self._vid = vid
        self._cid = cid
        self._nodes = nodes
        self._kin = k_in  # 结点内部的边的权重

class Louvain():
    def __init__(self, G):
        self._G = G
        self._m = 0  # 边数量
        self._cid_vertices = {}  # 需维护的关于社区的信息(社区编号,其中包含的结点编号的集合)
        self._vid_vertex = {}  # 需维护的关于结点的信息(结点编号，相应的Vertex实例)
        for vid in self._G.keys():
            self._cid_vertices[vid] = set([vid])
            self._vid_vertex[vid] = Vertex(vid, vid, set([vid]))
            self._m += sum([1 for neighbor in self._G[vid].keys() if neighbor > vid])

    def first_stage(self):
        mod_inc = False  # 用于判断算法是否可终止
        visit_sequence = self._G.keys()
        random.shuffle(list(visit_sequence))
        while True:
            can_stop = True  # 第一阶段是否可终止
            for v_vid in visit_sequence:
                v_cid = self._vid_vertex[v_vid]._cid
                k_v = sum(self._G[v_vid].values()) + self._vid_vertex[v_vid]._kin
                cid_Q = {}
                for w_vid in self._G[v_vid].keys():
                    w_cid = self._vid_vertex[w_vid]._cid
                    if w_cid in cid_Q:
                        continue
                    else:
                        tot = sum(
                            [sum(self._G[k].values()) + self._vid_vertex[k]._kin for k in self._cid_vertices[w_cid]])
                        if w_cid == v_cid:
                            tot -= k_v
                        k_v_in = sum([v for k, v in self._G[v_vid].items() if k in self._cid_vertices[w_cid]])
                        delta_Q = k_v_in - k_v * tot / self._m  # 由于只需要知道delta_Q的正负，所以少乘了1/(2*self._m)
                        cid_Q[w_cid] = delta_Q

                cid, max_delta_Q = sorted(cid_Q.items(), key=lambda item: item[1], reverse=True)[0]
                if max_delta_Q > 0.0 and cid != v_cid:
                    self._vid_vertex[v_vid]._cid = cid
                    self._cid_vertices[cid].add(v_vid)
                    self._cid_vertices[v_cid].remove(v_vid)
                    can_stop = False
                    mod_inc = True
            if can_stop:
                break
        return mod_inc

    def second_stage(self):
        cid_vertices = {}
        vid_vertex = {}
        for cid, vertices in self._cid_vertices.items():
            if len(vertices) == 0:
                continue
            new_vertex = Vertex(cid, cid, set())
            for vid in vertices:
                new_vertex._nodes.update(self._vid_vertex[vid]._nodes)
                new_vertex._kin += self._vid_vertex[vid]._kin
                for k, v in self._G[vid].items():
                    if k in vertices:
                        new_vertex._kin += v / 2.0
            cid_vertices[cid] = set([cid])
            vid_vertex[cid] = new_vertex

        G = collections.defaultdict(dict)
        for cid1, vertices1 in self._cid_vertices.items():
            if len(vertices1) == 0:
                continue
            for cid2, vertices2 in self._cid_vertices.items():
                if cid2 <= cid1 or len(vertices2) == 0:
                    continue
                edge_weight = 0.0
                for vid in vertices1:
                    for k, v in self._G[vid].items():
                        if k in vertices2:
                            edge_weight += v
                if edge_weight != 0:
                    G[cid1][cid2] = edge_weight
                    G[cid2][cid1] = edge_weight

        self._cid_vertices = cid_vertices
        self._vid_vertex = vid_vertex
        self._G = G

    def get_communities(self):
        communities = []
        for vertices in self._cid_vertices.values():
            if len(vertices) != 0:
                c = set()
                for vid in vertices:
                    c.update(self._vid_vertex[vid]._nodes)
                communities.append(c)
        return communities

    def execute(self):
        iter_time = 1
        while True:
            iter_time += 1
            mod_inc = self.first_stage()
            if mod_inc:
                self.second_stage()
            else:
                break
        return self.get_communities()

if __name__ == '__main__':
    G = load_graph(r'C:\\Users\\程勇\\Desktop\\similarity.txt')
    algorithm = Louvain(G)
    communities = algorithm.execute()
    # 按照社区大小从大到小排序输出
    communities = sorted(communities, key=lambda b: -len(b)) # 按社区大小排序
    count = 0
    for communitie in communities:
        count += 1
        print("社区", count, " ", communitie)
    


测试用例文件如图：



这是部分测试用例的截图，一行的前两个数是顶点编号，第三个数是权重。按照每个社区大小顺序从大到小打印：



$\quad$需要测试文件的话在评论区留下你的邮箱哦，求关注~

社区发现图法
社区发现算法思路
GN算法

社区发现算法思路

社区划分问题大多基于这样一个假设：同一社区内部的节点连接较为紧密，社区之间的节点连接较为稀疏。因此，社区发现本质上就是网络中结构紧密的节点的聚类。
从这个角度来说，这跟聚类算法一样，社区划分问题主要有两种思路：
       (1)凝聚方法(agglomerative method)：添加边
       (2)分裂方法(divisive method)：移除边


另一方面，我们也可以认为同一个社区内的节点，之所以能够聚集在一起，是因为它们有相似性。因此只要我们能够将一个节点很好地表示，成为一个向量，那么同样可以用相似性大法来寻找社区聚集，不过这点上需要向量对节点的描述足够好和足够完备。
GN算法据说是社区发现领域的第一个算法，或者说它开启了这个领域的研究。下面我们来分别介绍这个领域及其算法是如何演化的。
GN算法

计算每一条边的边介数
删除边界数最大的边；
重新计算网络中剩下的边的边阶数；
重复(3)和(4)步骤，直到网络中的任一顶点作为一个社区为止。

　　

GN算法的R分析代码

// An highlighted block
> library("igraph")
> karate  <-  graph.famous("Zachary")
> ebc <- edge.betweenness.community(karate)
> ebc
Graph community structure calculated with the edge betweenness algorithm
Number of communities (best split): 5 
Modularity (best split): 0.4012985 
Membership vector:
 [1] 1 1 2 1 3 3 3 1 4 5 3 1 1 1 4 4 3 1 4 1 4 1 4 4 2 2 4 2 2 4 4 2 4 4
> modularity(ebc)
[1] 0.4012985
> membership(ebc)
 [1] 1 1 2 1 3 3 3 1 4 5 3 1 1 1 4 4 3 1 4 1 4 1 4 4 2 2 4 2 2 4 4 2 4 4
> plot(ebc,karate)

模糊谱聚类重叠社区发现算法
Overlapping
Community
Discovery
Algorithm
Based
on
Fuzzy
Spectral
Clustering
【摘
要】
摘
要
:
为克服传统重叠社区发现算法产生局部最优解的缺陷，提出一
种新的基于模糊谱聚类的重叠社区发现算法。用局部连接相似度度量构造原始
样本数据集的相似度矩阵，并采用谱方法将原样本嵌入到一个低维空间。在这
个空间上，构造模糊相似矩阵，采用模糊聚类划分社区，检测并合并冗余社区。
试验结果表明，该算法能够有效地提高重叠社区划分的质量。
【期刊名称】
自动化仪表
【年
(
卷
),
期】
2016(037)003
【总页数】
4
【关键词】
关键词
:
模糊谱聚类
模糊理论
谱方法
重叠社区
相似度矩阵
冗余社区
二乘法
第一作者闫晓鹏
(1990
－
)
，女，现为江西师范大学软件工程专业在读硕士研究
生
;
主要从事本体论和语义
Web
、数据挖掘、社会网络分析方面的研究。
0
引言
早期的社区发现研究是针对非重叠社区，认为网络可以被分割成若干个互不相
连的社区，每个节点只能属于唯一的社区。然而，在实际的社交网络中，存在
一些节点同时隶属于不同的社区，且这些节点在社区间的信息传播和演变中起
着重要的中介或过滤的作用，能够衔接各个社区。为此，研究者们陆续提出一
系
列
算
法
来
挖
掘
网
络
重
叠
社
区
。
例
如
:
派
系
过
滤
算
法
(clique
percolation
method
，
CPM)
［
1
－
2
］
;
基
于
标
签
传
播
的
算
法
:
社
区
重
叠
传
播
算
法