精华内容
下载资源
问答
  • 社区发现

    千次阅读 2012-09-29 11:26:34
    社区要满足两个条件:一是社区的成员有共同的话题和爱好;二是社区的成员之间的联系相比和社区外的联系要紧密。 通过用户的搜索情况可以找到有相同爱好的人,这些人组成候选社区成员。比如用户搜索“NBA”,这个...

    社区要满足两个条件:一是社区的成员有共同的话题和爱好;二是社区的成员之间的联系相比和社区外的联系要紧密。

    通过用户的搜索情况可以找到有相同爱好的人,这些人组成候选社区成员。比如用户搜索“NBA”,这个用户就是候选的NBA社区成员。

    通过一定的算法计算这些成员间的紧密程度,大于一定阀值的成员共同组成了NBA社区。算法有HITS,类似于搜索引擎的链接分析,每个人都有一个H值和A值,迭代计算。也可以用聚类的算法,每个成员可以表示为一个向量,向量取值为1标识和另一个成员有联系,取0标识没有联系,通过聚类可以发现社区。这种方式还可以发现多个NBA社区。

    展开全文
  • 社区发现算法之——Louvain

    万次阅读 多人点赞 2018-10-25 09:13:39
    1、什么是社区 ...社区发现算法有很多,例如LPA,HANP,SLPA以及我们今天的主人公——Louvain。不同的算法划分社区的效果不尽相同。那么,如何评价这些算法孰优孰劣呢? 用模块度modularity来衡量。模...

    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 需要测试文件的话在评论区留下你的邮箱哦,求关注~

    展开全文
  • 社区发现理解

    千次阅读 2018-07-02 09:58:21
    最近一段时间工作上使用到了社区发现,虽然只是小小一部分。但是呢,工作量还是不小的,在网上找了很多的资料,也做了很多的研究性工作,看了非常多的paper,也做了一点小改进。那么来开始总结一下社区划分究竟怎么...

    最近一段时间工作上使用到了社区发现,虽然只是小小一部分。但是呢,工作量还是不小的,在网上找了很多的资料,也做了很多的研究性工作,看了非常多的paper,也做了一点小改进。那么来开始总结一下社区划分究竟怎么做,目前有哪些主流的做法以及他们的原理是什么。

    图,这里不是指图片的图喔。而是一个名字叫图的数据结构类型,由点和边构成。在我们的世界中怎么理解它呢?比如我们定义了北京,上海,广州为点,那么北京上海广州之间的所有交通形式都可以描述为边,比如高速公路是一条边,飞机航线是一条边,非常非常多的边和点加起来,就构成了地图,在数据结构中,叫做图。








    图最基本的结构可以只有两个点,一条边,也就是我们现在程序猴的生活。公司<---->宿舍。最复杂但是最形象的可以看看现在的互联网,是由非常多的路由器交换机为点,电线光纤等为边的图。我们的大脑,可以看成是非常多的神经元为点,神经元间的突触为边的图。

    说完这个大家应该对图有一个基本的了解了。那么实际生活中对于图有什么算法上的应用呢?

    当然有了。比如对于我们每天的快递和外卖配送问题,有鼎鼎大名的一系列车辆路径问题VRP(Vehicle Routing Problem),可以使得配送员走最短的路程,优化效率。比如朋友圈和社区发现,通过对于社交网络的划分,来发现各种小社区,对他们进行精准推送。以及路由分配算法,也属于最短路径的一种。

    总得来说,图算法的主要贡献在于,定义了一个复杂的非数组型结构,来对生活中的很多类似的问题进行简化模拟,进而寻找出能够优化现实中效率的算法。

    说了这么多社区发现又是什么玩意?

    社区划分就是在一个比较大图里,对它们进行区分,进而找到相同社区里面的点相对靠近,不同社区的点相对疏远,这样的算法。









    很多人听到这就蒙了,啥玩意,不要慌,你们手中的k-means,也就是k均值算法不就是社区发现的一种吗?无监督地找出k个能够划分的类别。这里就不深入谈它了,我们的重点还是图数据结构中的社区发现。

    目前来说,社区发现中只有两种主流的做法。第一种是cut,也就是划分,把无关联的边去掉,进而取到核心的社区。第二种是gather,也就是聚合,将关联性比较大的顶点聚集起来,关联性较小的顶点剔除出去。

    最简单的算法k-core decomposition,就是对图中的所有顶点进行判定,若度小于K,则将该点和所有关联的边从图中删除,然后再进行下一轮迭代,直到图中所有的顶的度都大于K。

    LOOP

    (1)找到小于K的点

    (2)删除步骤1找到的点和边

    (3)继续进行步骤1,若找不到符合条件的点则结束

    END






    这个算法有什么问题呢?最终得到的图结构非常简单,但是也非常零散,但是能够找到非常非常核心的组织中心。

    Label Propagation Algorithm标签传播算法,是属于第二种,是基于点聚合的一个算法。每个顶点在开始的时候都设立自己的标签,然后向所有的邻居进行广播。每个顶点在接收到广播的时候呢,将收到的最多的标签作为自己的标签,进行下一轮的迭代。

    初始化:(1)顶点标签

    LOOP

    (2)发送自己的标签

    (3)接收标签

    (4)将最大标签作为自己的标签

    (5)继续进行方法2,直到达到最大迭代次数。

    END


    这个算法的时间复杂度是线性的,无论多么复杂的图,一般在五次以内都能够比较准确地发现社区。但是有什么问题呢?结果会震荡。在星型网络和长链型网络中,结果会不断震荡。这又给我们带来了思考,是不是有更优的算法?答案是有的。

    在现实生活中,每个人都可能属于不同的社区,而LPA算法只能将顶点划分一个社区内,而且结果会震荡。接下来介绍的SLPA算法。Speaker Listener LabelLabel Propagation Algorithm。主要是LPA算法的升级版,改进点就在于,顶点在发送和接收的时候都可以有规则,而顶点的标签也从一个标签替换为一个Array,可以进行单顶点多社区的划分。

    初始化:(1)顶点标签

    LOOP

    (2)根据规则发送标签

    (3)接收标签,将标签以一定的规则追加到自己的标签中

    (4)继续进行方法2,直到达到最大迭代次数。

    END

    (5)对结果进行解析,自行决定单顶点社区的个数。

    这个结果不会有震荡,时间复杂度也跟LPA是一样的,只是空间复杂度上从O(N)变为O(kN),还算可以接受。

    SLAP社区划分的结构还算可以接受,那还有没有呢?答案是有的。

    HLAP,就是混合型LAP,王婷博士的成果,这个结果算最好。这个HLAP主要是基于二分图的一个算法,跟LAP思想差不多。主要流程是这样的。

    初始化:(1)只初始化图的一边

    LOOP:

    (2)发送自己的标签

    (3)接收标签

    (4)将最大标签作为自己的标签

    (5)继续进行方法2,直到达到最大迭代次数。

    END

    这个方法对于二分图效果较好。

    几乎讲完了LPA系列的算法,其实还有另外一个系列,也就是基于Modularity的一些算法,也就是要找到quan'qquan全局模块度最大的最优解,或者局部最优解。这个系列的算法普遍时间复杂度比较高。


    模块度(modularity)指的是网络中连接社区结构内部顶点的边所占的比例,减去在同样的社团结构下任意连接这两个节点的比例的期望值

    这类算法的过程大概如下。

    初始化:(1)将各个顶点划分到不同的社区

    LOOP

    (2)尝试将自己划分到所有有关联的社区中

    (3)计算△Q,并将自己添加到模块度增加最大的社团中

    (4)重复步骤2直到模块度不再增加

    END











    相当多的算法都是在计算模块度这里下功夫。

    而有的算法从局部最优变为全局最优,不再看本社团的模块度,而是从全局上进行优化,计算复杂度增高,算法收敛比较慢,但是划分结果比较理想。好了讲一半,下次继续讲,手好酸妈蛋。

    欢迎大家留言交流。

    感谢大家一直的支持,随便来点都好开心。

    展开全文
  • 社区发现算法综述

    千次阅读 2019-01-16 19:54:38
    社区发现算法综述一个社区发现算法PPT 一个社区发现算法PPT 链接: https://blog.csdn.net/itplus/article/details/9286905

    社区发现算法综述

    一个社区发现算法PPT

    链接: https://blog.csdn.net/itplus/article/details/9286905

    展开全文
  • 社区发现数据集

    万次阅读 多人点赞 2016-04-07 23:09:05
    社区发现数据集目录社区发现数据集目录 基于链接分析的数据集 基于链接与离散型属性的数据集 基于链接与文本型属性的数据集 其他常见的数据集链接基于链接分析的数据集 Zachary karate club Zachary 网络是通过对一...
  • 社区发现算法

    千次阅读 2017-07-03 01:52:48
    社区发现算法一.原始LPA算法 引用 https://greatpowerlaw.wordpress.com/2013/02/08/community-detection-lpa/ 算法原理 标签传播算法是不重叠社区发现的经典算法,其基本思想是:将一个节点的邻居节点的标签中数量...
  • 社区发现综述

    千次阅读 2016-09-28 15:31:42
    最近做社区发现方向:  一些好的community detection 博客文章地址:  community detection (1):http://blog.csdn.net/cmonkey_cfj/article/details/18680375  community detection (2):...
  • 利用GN算法进行社区发现

    千次阅读 2019-06-23 11:26:53
    Python实现--利用GN算法进行社区发现
  • 传统的GN算法只适用于无向无权图的社区发现,通过对边介数进行调整得到无向有权图的GN算法实现
  • lpa社区发现

    千次阅读 2016-03-22 10:39:00
    with dense connections within groups and only sparser connections between them" (Newman, 2004)...当前所用的一些社区发现算法,需要先验信息,比如社团的数目和大小,或者计算量很大。LPA算法只需要使用网络结构
  • 社区发现的一些算法

    千次阅读 2015-12-22 22:06:33
    近期想对社区发现领域进行一下简单研究,看到一篇不错的文章,文章是根据国防科大骆志刚教授的论文《复杂网络社团发现算法研究新进展》整理的,主要是对社区发现的一些算法进行简单分析。 一、基于模块度优化的...
  • 社区发现GN算法 采用python编程加以实现 可直接运行。资源很好,有分的尽量下载一下。
  • 社区发现评价指标Q和NMI讲解、代码实现 文章目录社区发现评价指标Q和NMI讲解、代码实现模块度Q标准化互信息NMI代码实现参考文献 模块度Q 2004年Newman等人提出了模块度Q,之后广泛应用于衡量社区的划分质量,下面...
  • 基于Python3的社区发现算法fast_unfolding,已经对其中的bug进行修改
  • 基于Networkx的社区发现算法(FN)

    千次阅读 热门讨论 2019-11-15 15:38:29
    基于Networkx的FN社区发现算法 目录基于Networkx的FN社区发现算法参考资料数据下载代码 参考资料 本文基于复杂网络分析库——Networkx: 1、Networkx官网: Networkx. 2、找到一篇FN算法的讲解,但是用Matlab实现的...
  • Python社区发现—Louvain—networkx和community

    万次阅读 热门讨论 2020-03-15 22:51:59
    社区 如果一张图是对一片区域的描述的话,将这张图划分为很多个子图。...Louvain算法是基于模块度的社区发现算法,该算法在效率和效果上都表现较好,并且能够发现层次性的社区结构,其优化目标是最大化...
  • 社区发现(Community Detection)算法

    万次阅读 多人点赞 2018-05-30 10:01:32
    社区发现(Community Detection)算法用来发现网络中的社区结构,也可以看做是一种聚类算法。以下是我的一个 PPT 报告,分享给大家。 从上述定义可以看出:社区是一个比较含糊的概念,只给出了一个定性的刻画。另外...
  • 模块度与Louvain社区发现算法

    千次阅读 2017-08-02 11:23:01
    Louvain算法是基于模块度的社区发现算法,该算法在效率和效果上都表现较好,并且能够发现层次性的社区结构,其优化目标是最大化整个社区网络的模块度。 模块度(Modularity )  模块度是评估一个社区网络...
  • 社区发现算法总结(一)

    万次阅读 2019-07-02 15:30:59
    在做东西的时候用到了社区发现的算法,因此查找了好多人的文章,发现一个不错的总结,先转载过来 原文出处http://blog.csdn.net/aspirinvagrant/article/details/45577033 在社区发现算法中,几乎不可能先确定...
  • 社区发现 -- 数据挖掘

    千次阅读 2018-05-05 16:25:00
    图聚类,也称为社区发现、图划分,其与聚类相似又不同于聚类(旨在将相似的数据点划分为一类),社区发现的目的是通过将数据点划分到不同的簇中,使得簇内的边尽量地多,簇之间的边尽可能地少。 社区发现 ...
  • Graphx社区发现算法学习

    千次阅读 2017-03-10 19:17:15
    对这些网络进行社区发现具有极大的意义,如在人际关系网中,可以发现出具有不同兴趣、背景的社会团体,方便进行不同的宣传策略;在交易网中,不同的社区代表不同购买力的客户群体,方便运营为他们推荐合适的商品;在...
  • 社区发现算法————总结

    千次阅读 2018-12-25 15:32:43
    开始了解社区发现的时候,我以为这只是一种算法。后来深入下去才知道,它的状态是,上有老下有小的情况。 向上走:社区发现 ∈\in∈ 复杂网络聚类 ∈\in∈ 图论 由于项上走实在知识面太广,有待后期学习。所以决定先...
  • 社区发现可视化(python3+networkx)

    千次阅读 2019-12-23 18:59:51
    网上搜了一些社区发现可视化的代码,发现GitHub上有几个不错的可视化案例,如 https://github.com/networkanddatasciencelab/SNA-Community-Detection ... ...
  • 社区发现(六)--模块度

    千次阅读 2019-06-09 15:35:13
    社区发现算法中,几乎不可能先确定社区的数目,于是,必须有一种度量的方法,可以在计算的过程中衡量每一个结果是不是相对最佳的结果。 模块度(Modularity)用来衡量一个社区的划分是不是相对比较好的结果。一个...
  • 社区发现(一)--算法综述

    千次阅读 2019-06-09 14:58:25
    1. 社区发现简介 社区,从直观上来看,是指网络中的一些密集群体,每个社区内部的结点间的联系相对紧密,但是各个社区之间的连接相对来说却比较稀疏(图1,当然社区的定义不止有这一种)。这样的社区现象被...
  • 【图算法】社区发现算法——Fast unfolding1. 社区划分问题的定义:2. 社区划分的评价标准:3. Fast unfolding算法:3.1 Fast Unfolding算法的基本思路:3.2 算法流程:4. 代码实现:4.1 Python实现:4.2 算法测试:...
  • COPRA算法[1]是Gregory在2010年提出的一种基于标签传递的社区发现算法,该算法可以看作是RAK算法[2]的改进算法。COPRA算法对RAK算法的最大改进在于其可以进行重叠社区的发现,而RAK算法只能用于非重叠社区的发现。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 281,595
精华内容 112,638
关键字:

社区发现