精华内容
下载资源
问答
  • GN算法
    2022-02-10 21:31:41

    🎋开发平台:jupyter lab

    🎠编程语言:python3.x

    1. GN算法的简介

    GN算法:一个经典的社区发现算法,它属于分裂的层次聚类算法。最初,由Michelle Girvan和Mark Newman提出。
    基本思想:不断的删除网络中具有相对于所有源节点的最大的边介数的边,然后,再重新计算网络中剩余的边的相对于所有源节点的边介数,重复这个过程,直到网络中,所有边都被删除。

    1.1 GN算法涉及的概念

    (1)模块度Q,也称模块化度量值,是评价社区的结构强度的指标。指标结果越大,社区划分效果越好。

    • 模块度的计算公式如下:
      在这里插入图片描述
      其中Q是模块度,M是网络中边的数量。综上,GN算法的整体流程如图2.1所示。

    (2)边介数(Betweenness):网络中经过每条边的最短路径的数目。

    1.2 GN算法实现的步骤

    • 计算网络中所有边的介数;
    • 找到介数最高的边并将它从网络中移除;
    • n 重复,直到每个节点就是一个社团为止;

    2. GN的实现及其可视化

    • 算法结构:
      在这里插入图片描述

    2.1 数据文件(data.txt)

    1 2
    1 3
    2 3
    4 5
    4 6
    5 6
    9 10
    9 11
    10 11
    12 13
    12 14
    13 14
    3 7
    6 7
    7 8
    8 9
    8 12
    8 15
    15 16
    16 17
    15 17
    

    2.2 GN算法实现

    • 工具类方法
    #util.py文件
    #coding=utf-8
    import networkx as nx
    import random
    
    # 加载网络
    def load_graph(path):
       G = nx.Graph()
       with open(path) as text:
           for line in text:
               vertices = line.strip().split(" ")
               source = int(vertices[0])
               target = int(vertices[1])
               G.add_edge(source, target)
       return G
    
    # 克隆
    def clone_graph(G):
       cloned_graph = nx.Graph()
       for edge in G.edges():
           cloned_graph.add_edge(edge[0], edge[1])
       return cloned_graph
    
    # 计算Q值
    def cal_Q(partition, G):
       m = len(list(G.edges()))  #边的个数
       a = []
       e = []
    
       # 计算每个社区的a值
       for community in partition:
           t = 0
           for node in community:
               t += len(list(G.neighbors(node)))
           a.append(t / float(2 * m))
    
       # 计算每个社区的e值
       for community in partition:
           t = 0
           for i in range(len(community)):
               for j in range(len(community)):
                   if i != j:
                       if G.has_edge(community[i], community[j]):
                           t += 1
           e.append(t / float(2 * m))
    
       # 计算Q
       q = 0
       for ei, ai in zip(e, a):
           q += (ei - ai ** 2)
       return q
    
    ##获取随机颜色
    colors = []
    def get_color():
       global colors #声明我们在函数内部使用的是在函数外部定义的全局变量a
       colorArr = ['1','2','3','4','5','6','7','8','9','A','B','C','D','E','F']
       color = ""
       for i in range(6):
           color += colorArr[random.randint(0,14)]
       if color in colors:
           color = get_color()
           ###防止陷入死循环,设置颜色数组最大长度
           if len(colors)==50:
               colors = []
       else:
           colors.append(color)
       return color
    
    • GN算法类及其主函数
    #GN.py文件
    # coding=utf-8
    # 首先导入包
    import networkx as nx
    import matplotlib.pyplot as plt
    
    class GN(object):
      """docstring for GN"""
    
      def __init__(self, G):
          self._G_cloned = clone_graph(G)
          self._G = G
          self._partition = [[n for n in G.nodes()]]
          self._max_Q = 0.0
    
      # GN算法
      def execute(self):
          while len(self._G.edges()) > 0:
              # 1.计算所有边的edge betweenness
              edge = max(nx.edge_betweenness(self._G).items(),
                         key=lambda item: item[1])[0]
              # 2.移去edge betweenness最大的边
              self._G.remove_edge(edge[0], edge[1])
              # 获得移去边后的子连通图
              components = [list(c) for c in list(nx.connected_components(self._G))]
              if len(components) != len(self._partition):
                  # 3.计算Q值
                  cur_Q = cal_Q(components, self._G_cloned)
                  # print(cur_Q)
                  if cur_Q > self._max_Q:
                      self._max_Q = cur_Q
                      self._partition = components
          print('-----------the Divided communities and the Max Q-----------')
          print('Max_Q:', self._max_Q)
          print('The number of Communites:', len(self._partition))
          print("Communites:", self._partition)    
          return self._partition
    
    
    # 可视化划分结果
    def showCommunity(G, partition, pos):
      # 划分在同一个社区的用一个符号表示,不同社区之间的边用黑色粗体
      cluster = {}
      labels = {}
      for index, item in enumerate(partition):
          for nodeID in item:
              labels[nodeID] = r'$' + str(nodeID) + '$'  # 设置可视化label
              cluster[nodeID] = index  # 节点分区号
    
      # 可视化节点
    #     colors = ['r', 'g', 'b', 'y', 'm']
      shapes = ['v', 'D', 'o', '^', '<']
      ### [217, 13, 14]
      for index, item in enumerate(partition):
          nx.draw_networkx_nodes(G, pos, nodelist=item,
                                 node_color="#"+get_color(),
                                 node_shape=shapes[random.randint(0,102)%4],
                                 node_size=350,
                                 alpha=1)
    
      # 可视化边
      edges = {len(partition): []}
      for link in G.edges():
          # cluster间的link
          if cluster[link[0]] != cluster[link[1]]:
              edges[len(partition)].append(link)
          else:
              # cluster内的link
              if cluster[link[0]] not in edges:
                  edges[cluster[link[0]]] = [link]
              else:
                  edges[cluster[link[0]]].append(link)
    
      for index, edgelist in enumerate(edges.values()):
          # cluster内
          if index < len(partition):
              nx.draw_networkx_edges(G, pos,
                                     edgelist=edgelist,
                                     width=1, alpha=0.8, edge_color="#"+get_color())
          else:
              # cluster间
              nx.draw_networkx_edges(G, pos,
                                     edgelist=edgelist,
                                     width=3, alpha=0.8, edge_color="#"+get_color())
    
      # 可视化label
      nx.draw_networkx_labels(G, pos, labels, font_size=12)
    
      plt.axis('off')
      plt.show()
    
    
    if __name__ == '__main__':
      # 加载网络数据并可视化
      G = load_graph("./data.txt")
      pos = nx.spring_layout(G)
      nx.draw(G, pos, with_labels=True, font_weight='bold')
      plt.show()
    
      # GN算法
      algo = GN(G)
      partition = algo.execute()
      #print(partition)
    
      # 可视化结果
      showCommunity(algo._G_cloned, partition, pos)
    

    2.3 运行结果

    在这里插入图片描述

    3.参考文章

    (1)【复杂网络社团发现】GN算法步骤详解(附python代码实现).
    (2) 【复杂网络社区发现】社区网络算法之GN算法.
    (3) 【复杂网络社团发现】Gephi绘制网络图.
    (4) 【复杂网络社团发现】GN算法边介数详解.

    更多相关内容
  • gn算法matlab代码 :herb: 先进的数据结构 JavaScript中数据结构的游乐场。 这是的子项目,是的双子项目。 :newspaper: 描述 该自述文件重新组合了许多项目,这些项目侧重于使用JavaScript实现数据结构。 该项目本身...
  • GN算法Java版源码,个人鼎作 我采用压缩矩阵三元组的形式存储数组的,极大地节省了空间,经过反复测试数据,程序达到了perfect!! 也是我个人本科阶段毕业设计的其中一个算法!!
  • GN算法python实现

    2019-01-11 10:42:42
    可以直接运行的GN社区发现算法用户python实现,对应输出结果以csv文件
  • gn算法matlab代码OpenWasteWater(OpenModelica库) 与Openmodelica() 主要作者: 约阿希姆·贝伦特(Joachim Behrendt) 汉堡工业大学废水管理与水保护研究所艾森道夫大街42 21073汉堡,德国电子邮件: 动机 该...
  • GN分裂算法的MATLAB实现,可以很好的学习用GN算法进行社团划分
  • gn算法matlab代码 JavaScript中数据结构的游乐场。 这是的子项目,是的双子项目。 描述 这个专案只是任何不适合任何专案的资料结构的游乐场, 堆 :JavaScript的堆数据结构 :JavaScript中堆数据结构的规范 :Python...
  • 基于matlab实现经典算法GN,输入矩阵,输出社区结果
  • gn算法matlab代码第二个拉普拉斯特征值 第二个最小的标准化Laplacian特征值及其应用的调查。 第二个最小的归一化拉普拉斯特征值(我简称为lambda2 )与图的连通性密切相关。 Cheeger不等式指出,一个较小的图可以很...
  • gn算法matlab代码地理位置 Matlab的简单地理位置代码 在此存储库中,可以找到用于传感器网络的三种不同地理位置技术的简单Matlab实现:最小二乘算法(LS),高斯牛顿算法(GN),基于泰勒级数展开的基于DOA的因子图...
  • 简单网络的matlab算法,输出的cut矩阵是分区
  • 基于GN算法的文献聚类方法研究.pdf
  • gn算法实现

    2018-03-15 10:47:31
    实现gn算法,实现把一些数据集分成 一个或者两个集团!
  • GN算法的java实现

    2019-01-19 12:36:31
    GN算法的一个例子,就是先确定节点之间的邻接关系,然后,根据这个来做聚类划分,最后得到相应的社团。
  • GN算法

    万次阅读 2018-12-28 16:13:02
    社区发现算法(二) 2015年05月09日 10:17:00 GeekStuff 阅读数:19848 版权声明:本文为博主原创文章,未经博主允许不得转载。... GN算法   本算法的具体内容请参考F...

    社区发现算法(二)

    2015年05月09日 10:17:00 GeekStuff 阅读数:19848

    版权声明:本文为博主原创文章,未经博主允许不得转载。http://blog.csdn.net/aspirinvagrant https://blog.csdn.net/fenghuangdesire/article/details/45599071

    GN算法

     

    本算法的具体内容请参考Finding and evaluating community structure in networks(Newman and Girvan)

    重要概念

    边介数(betweenness):网络中任意两个节点通过此边的最短路径的数目。


    GN算法的思想:

    在一个网络之中,通过社区内部的边的最短路径相对较少,而通过社区之间的边的最短路径的数目则相对较多。下图中展示了变得强度以及边介数在现实网络中的分布情况。GN算法是一个基于删除边的算法,本质是基于聚类中的分裂思想,在原理上是使用边介数作为相似度的度量方法。在GN算法中,每次都会选择边介数高的边删除,进而网络分裂速度远快于随机删除边时的网络分裂。

     

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

    GN算法示例:


    GN算法计算边界数的时间复杂度为 O(m*n),总时间复杂度在m条边和n个节点的网络下为 O(m2*n)。
    GN算法的缺陷:
    (1)不知道最后会有多少个社区;
    (2)在计算边介数的时候可能会有很对重复计算最短路径的情况,时间复杂度太高;
    (3)GN算法不能判断算法终止位置。
    为了解决这些问题,Newman引入了模块度Q的概念,它用来一个评价社区结构划分的质量。网络中的社区结构之间的边数并不是绝对数量上的少,而是应该比期望的边数要少。关于模块度的概念请参考社区划分的标准--模块度

    GN算法具体实现借助基于R的图挖掘库igraph
    数据集为Karate数据集:
    Zachary空手道俱乐部成员关系网络是复杂网络、社会学分析等领域中最常用的一个小型检测网络之一。从1970到1972年,Zachary观察了美国一所大学空手道俱乐部成员间的社会关系,并构造出了34个成员,78条成员关系的社会关系网。两个成员经常一起出现在俱乐部活动之外的其他场合,就认为两个成员间有边。该俱乐部因为主管(节点34)与教练(节点1)之间的争执而分裂成2个各自为核心的小俱乐部。结构如下图所示。具体请参考An information flow model for conflict and fission in small groups

    GN算法的R分析代码

     

    > 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)

     

     

     

     

     

    Newman快速算法 

    本算法的具体内容请参考Fast algorithm for detecting community structure in networks(Newman)

    GN算法通过模块度可以准确的划分网络,但它只适用于中小型规模的网络。Newman提出一种基于贪心的快速社区发现算法,算法的基本思想是:首先将网络中的每个顶点设为一个单独社区,然后选出使得模块度Q的增值最大的社区对进行合并;如果网络中的顶点属于同一个社区,则停止合并过程。整个过程是自底向上的过程,且这个过程最终得到一个树图,即树的叶子节点表示网络中的顶点,树的每一层切分对应着网络的某个具体划分,从树图的所有层次划分中选择模块度值最大的划分作为网络的有效划分。

     

    设网络有n个节点,m条边,每一步合并对应的社区数目为r,组成一个r*r矩阵e,矩阵元素eij表示社区i中的节点与社区j中节点之间连边的数目在网络总变数的百分比。

    主要步骤:

    (1) 初始化网络,开始网络有n 个社区,初始化的eij和ai为:

    (2)依次按照∆Q的最大或者最小的方向进行合并有边相连的社区对,并计算合并后的模块度增量∆Q:

    (3)合并社区对以后修改对社区对称矩阵e 和社区i和j对应的行列;

    (4)重复执行步骤(2)和(3),不断合并社区,直至整个网络合并成一个社区为止。

    Newman快速算法的R分析代码

     

    >  karate  <-  graph.famous("Zachary")
    >  fc  <-  fastgreedy.community(karate)
    >  dendPlot(fc)

     

     

     

     

     

    参考资料:

    Social and Information Network Analysis Jure Leskovec, Stanford University

    展开全文
  • 社区发现算法——GN算法与FN算法

    千次阅读 热门讨论 2022-02-04 10:28:28
    GN算法 本算法的具体内容请参考Finding and evaluating community structure in networks(Newman and Girvan)。 重要概念 边介数(betweenness):网络中任意两个节点通过此边的最短路径的数目。 GN算法的思想: ...

    GN算法

    本算法的具体内容请参考Finding and evaluating community structure in networks(Newman and Girvan)

    重要概念

    边介数(betweenness):网络中任意两个节点通过此边的最短路径的数目。

    GN算法的思想:

    在一个网络之中,通过社区内部的边的最短路径相对较少,而通过社区之间的边的最短路径的数目则相对较多。GN算法是一个基于删除边的算法,本质是基于聚类中的分裂思想,在原理上是使用边介数作为相似度的度量方法。在GN算法中,每次都会选择边介数高的边删除,进而网络分裂速度远快于随机删除边时的网络分裂。

    GN算法的步骤如下:
    (1)计算每一条边的边介数;
    (2)删除边界数最大的边;
    (3)重新计算网络中剩下的边的边阶数;
    (4)重复(3)和(4)步骤,直到网络中的任一顶点作为一个社区为止。
    在这里插入图片描述
    GN算法计算边界数的时间复杂度为 O(m*n),总时间复杂度在m条边和n个节点的网络下为 O(m^2 *n)。
    GN算法的缺陷:
    (1)不知道最后会有多少个社区;
    (2)在计算边介数的时候可能会有很对重复计算最短路径的情况,时间复杂度太高;
    (3)GN算法不能判断算法终止位置。
    为了解决这些问题,Newman引入了模块度Q的概念,它用来一个评价社区结构划分的质量。网络中的社区结构之间的边数并不是绝对数量上的少,而是应该比期望的边数要少。

    模块度

    模块度介绍

    设Avw为网络的邻接矩阵的一个元素,定义为:

    img

    假设cv和cw分别表示点v和点w所在的两个社区,社区内部的边数和网络中总边数的比例

    img

    函数δ(cv,cw)的取值定义为:如果v和w在一个社区,即cv=cw,则为 1,否则为 0。m 为网络中边的总数。

    模块度的大小定义为社区内部的总边数和网络中总边数的比例减去一个期望值,该期望值是将网络设定为随机网络时同样的社区分配所形成的社区内部的总边数和网络中总边数的比例的大小,于是模块度Q为:

    img

    其中kv表示点v的度。

    img

    设eij表示社区I和社区J之间的连接边和与总边数的比例,ai表示社区i内部的点所关联的所有的边的数目与总边数的比例。

    img img

    为了简化Q的计算,假设网络已经划分成n个社区,这个时候就有一个 n维矩阵,Q 的计算可以变成:

    eii表示的是节点全在社区i内部中的边所占的比例

    img

    模块度的物理意义是,网络中连接两个同种类型结点的边(即社区内部的边)的比例减去在同样的社区结构”下任意连接节点的边的比例的期望值。如果社区内部边的比例不大于任意连接时的期望值,则有Q=0。Q的上限为1,而Q越接近于这个值,就说明社区结构越明显。实际网络中,该值通常位于0.3-0.7之间。

    引入模块度后代码如下:

    1. 计算当前网络的边介数和模块度Q值,并存储模块度Q值和当前网络中社团分割情况
    2. 除去边介数最高的边;
    3. 计算当前网络的模块度Q值,如果此Q值比原来的大,则将现在的Q值和网络中社团分割情况存储更新,否则,进行下一次网络分割;
    4. 所有边分割完毕,返回当前的模块度Q值和community分割情况。

    数据集为Karate数据集:
    Zachary空手道俱乐部成员关系网络是复杂网络、社会学分析等领域中最常用的一个小型检测网络之一。从1970到1972年,Zachary观察了美国一所大学空手道俱乐部成员间的社会关系,并构造出了34个成员,78条成员关系的社会关系网。两个成员经常一起出现在俱乐部活动之外的其他场合,就认为两个成员间有边。该俱乐部因为主管(节点34)与教练(节点1)之间的争执而分裂成2个各自为核心的小俱乐部。

    python代码如下:

    class GN:
        def __init__(self, G):
            self._G = G
            self._G_cloned = cloned_graph(G)
            # 初始划分情况为所有节点为一个社区
            self._partition = [[n for n in G.nodes()]]
            self._max_Q = 0.0
    
        def execute(self):
            while len(self._G.edges()) != 0:
                # 1.计算每一条边的边介数
                # nx.edge_betweenness返回边介数字典,items返回可遍历的(键, 值) 元组数组。这里每个item是((vi,vj), edge_betweenness))
                # 因此我们取的item[1]最大的item,再取该最小item的[0],为我们要删除的两个点(即要删除的边)
                edge = max(nx.edge_betweenness_centrality(self._G).items(),
                           key=lambda item: item[1])[0]
                # 2. 移去边介数最大的边
                self._G.remove_edge(edge[0], edge[1])
                # 获得移去边后的子连通图
                components = [list(c)
                              for c in list(nx.connected_components(self._G))]
                if len(components) != len(self._partition):
                    # 3. 计算Q值
                    cur_Q = cal_Q(components, self._G_cloned)
                    if cur_Q > self._max_Q:
                        self._max_Q = cur_Q
                        self._partition = components
            print(self._max_Q)
            print(self._partition)
            return self._partition
    

    结果如下:
    在这里插入图片描述
    Q值:0.40129848783694944
    算法执行时间0.08202219009399414

    Newman快速算法 (FN算法)

    本算法的具体内容请参考 Fast algorithm for detecting community structure in networks(Newman)

    GN算法通过模块度可以准确的划分网络,但它只适用于中小型规模的网络(时间复杂度高)。Newman提出一种基于贪心的快速社区发现算法,算法的基本思想是:首先将网络中的每个顶点设为一个单独社区,每次迭代选择产生最大Q值两个社团合并,直至整个网络融合成一个社团。整个过程是自底向上的过程,且这个过程最终得到一个树图,即树的叶子节点表示网络中的顶点,树的每一层切分对应着网络的某个具体划分,从树图的所有层次划分中选择模块度值最大的划分作为网络的有效划分。该算法的总体时间复杂度为O(m(m+n))

    设网络有n个节点,m条边,每一步合并对应的社区数目为r,组成一个r*r矩阵e,矩阵元素eij表示社区i中的节点与社区j中节点之间连边的数目在网络总变数的百分比。

    主要步骤:

    (1) 初始化网络,开始网络有n 个社区,初始化的eij和ai为:img

    (2)依次按照∆Q的最大或者最小的方向进行合并有边相连的社区对,并计算合并后的模块度增量∆Q:

    img

    (3)合并社区对以后修改对社区对称矩阵e 和社区i和j对应的行列;

    (4)重复执行步骤(2)和(3),不断合并社区,直至整个网络合并成一个社区为止。

    img
    python代码如下:

    class FastNewman:
        def __init__(self, path):
            self.G = load_graph(path)
            # G = nx.read_gml('dolphins.gml')
            self.A = nx.to_numpy_array(self.G)  # 邻接矩阵
            self.num_node = len(self.A)  # 点数
            self.num_edge = sum(sum(self.A))  # 边数
            self.c = {}  # 记录所有Q值对应的社团分布
    
            # def merge_community(self, iter_num, detaQ, e, b):
        #     # 一起合并容易出bug  查询的结果I在遍历过程中 可能在已经前面某次作为J被合并了
        #     # 比如某次是[ 3, 11] [11, 54] 第一轮迭代中11被合并 第二轮54合并到旧的11中  会导致后面被删除 导致节点消失  需要将54合并到现在11所在位置  比较麻烦 不如一个个合并
        #     b_num = sum([len(i) for i in b])
        #     det_max = np.amax(detaQ)
        #
        #     (I, J) = np.where(detaQ == det_max)
        #     print((I, J) )
        #     # 由于先遍历的I I中可能有多个相同值  所以合并时候因应该将J合并到I中
        #     # 如果将I合并到J中 后续删除删不到
        #     for m in range(len(I)):
        #         # 确保J还未被合并
        #         if J.tolist().index(J[m]) == m:
        #             # 将第J合并到I 然后将J清零
        #             e[I[m], :] = e[J[m], :] + e[I[m], :]
        #             e[J[m], :] = 0
        #             e[:, I[m]] = e[:, J[m]] + e[:, I[m]]
        #             e[:, J[m]] = 0
        #             b[I[m]] = b[I[m]] + b[J[m]]
        #
        #     e = np.delete(e, J, axis=0)
        #     e = np.delete(e, J, axis=1)
        #     J = sorted(list(set(J)), reverse=True)
        #     for j in J:
        #         b.remove(b[j])  # 删除第J组社团,(都合并到I组中了)
        #     b_num2 = sum([len(i) for i in b])
        #     if b_num2 != b_num:
        #         print("111")
        #     self.c[iter_num] = b.copy()
        #     return e, b
    
        def merge_community(self, iter_num, detaQ, e, b):
            # 一个个合并
            (I, J) = np.where(detaQ == np.amax(detaQ))
            # 由于先遍历的I I中可能有多个相同值  所以合并时候因应该将J合并到I中
            # 如果将I合并到J中 后续删除删不到
            e[I[0], :] = e[J[0], :] + e[I[0], :]
            e[J[0], :] = 0
            e[:, I[0]] = e[:, J[0]] + e[:, I[0]]
            e[:, J[0]] = 0
            b[I[0]] = b[I[0]] + b[J[0]]
    
            e = np.delete(e, J[0], axis=0)
            e = np.delete(e, J[0], axis=1)
            b.remove(b[J[0]])  # 删除第J组社团,(都合并到I组中了)
            self.c[iter_num] = b.copy()
            return e, b
    
        def Run_FN(self):
            e = self.A / self.num_edge  # 社区i,j连边数量占总的边的比例
            a = np.sum(e, axis=0)  # e的列和,表示与社区i中节点相连的边占总边数的比例
            b = [[i] for i in range(self.num_node)]  # 本轮迭代的社团分布
            Q = []
            iter_num = 0
            while len(e) > 1:
                num_com = len(e)
                detaQ = -np.power(10, 9) * np.ones((self.num_node, self.num_node))  # detaQ可能为负数,初始设为负无穷
                for i in range(num_com - 1):
                    for j in range(i + 1, num_com):
                        if e[i, j] != 0:
                            detaQ[i, j] = 2 * (e[i, j] - a[i] * a[j])
                if np.sum(detaQ + np.power(10, 9)) == 0:
                    break
    
                e, b = self.merge_community(iter_num, detaQ, e, b)
    
                a = np.sum(e, axis=0)
                # 计算Q值
                Qt = 0.0
                for n in range(len(e)):
                    Qt += e[n, n] - a[n] * a[n]
                Q.append(Qt)
                iter_num += 1
            max_Q, community = self.get_community(Q)
            return max_Q, community
    
        def get_community(self, Q):
            max_k = np.argmax(Q)
            community = self.c[max_k]
            return Q[max_k], community
    

    运行结果如下:在这里插入图片描述
    Q值:0.3806706114398422
    算法执行时间0.00400090217590332
    可以看到与GN算法相比,GN算法模块度略微下降,但执行时间快了很多。

    代码与数据集下载

    展开全文
  • 传统的GN算法只适用于无向无权图的社区发现,通过对边介数进行调整得到无向有权图的GN算法实现
  • GN算法 MATLAB

    2017-04-17 09:40:22
    GN算法 MATLAB
  • matlab复杂网络 gn算法

    2019-03-20 09:11:29
    matlab复杂网络代码,很好用希望大家喜欢
  • 用于社区结构划分,GN算法是最受认可的社区结构划分算法
  • 利用python编写的GN算法,可发现网络中的社团,本算法采用模块化系数作为评价标准,具体可以参考博客的有关内容
  • GN算法模块度GN算法模块度.pdf
  • 社区发现算法--GN算法

    2021-09-22 22:25:45
     GN算法提出了 边介数 的概念来解决该问题, 边介数: 某条边的边介数是指网络中通过这条边的最短路径的数目 GN算法的基本流程如下: 1)计算网络中各条边的边介数; 2)找出边介数最大的边,并将它移除(如果最大边...

    复杂网络发展
    1998年Watts和Strogtz提出了WS小世界模型(Small-world network)
    1999年Barabasi和Albert提出无标度网络模型(Scale-free network)
    人们发现复杂网络具有一定的社区结构。相同类型节点之间连接较多,构成一个一个的小社区,不同类型节点之间连接较少,但成为沟通不同社区的重要通道,这种连接的不均匀性表明,网络内部存在一定的自然分化

    社区定义:
    对于社区(community),目前没有明确的定义,常见的是Newman和Gievan提出的:社区是图的一个子图,相比于图的其他部分,其中包含着密集的节点,或者等价地说,如果图一个子图内部的链接数量高于这些子图之间的链接数,我们就可以说这个图含有社区
    GN算法的思想很直接,按定义来分割: 因为社区内部边连接较多,节点比较紧密,而社区之间边连接比较少,GN算法思想就是直接去除社区之间的边来分割社区;这里的关键问题是怎么识别社区之间的边呢? 或者说有什么指标能指示边是社区之间边的可能性? 
    GN算法提出了 边介数 的概念来解决该问题, 
    边介数: 某条边的边介数是指网络中通过这条边的最短路径的数目
    GN算法的基本流程如下:
        1)计算网络中各条边的边介数;
        2)找出边介数最大的边,并将它移除(如果最大边介数的边不唯一,那么既可以随机挑 选一条边断开也可以将这些边同时断开);
        3)重新计算网络中剩余各条边的边介数;
        4)重复第2)、3)步,直到网络中所有的边都被移除。
    优点:
    1、在知道划分社团数量时,可以较为精确的给出社团的划分结果;
    2、可以给出不同程度的社团划分结果,可以揭示关于网络层次结构的信息;
    缺点:
    1、在计算边介数的时候可能会有很多重复计算最短路径的情况,时间复杂度太高;
    2、若无法知道应该划分社团的数量,算法效果会相对较差;
    使用场景:
    1、已知社区个数
    2、计算量巨大,网络为中型网络过十万级别节点就非常慢了,亲测 doge

    不能po生成数据和代码 用了karate_club数据demo

     

     

     

     

    展开全文
  • 社区发现算法专题之 GN算法

    千次阅读 2021-05-27 21:59:17
    本文讲述社区发现之GN算法,并给出在karate club实验数据集下的实验示例代码
  • 何谓社区发现 在社交网络分析与挖掘中,社区发现是一个常用且重要的应用。 俗话说,物以类聚,人以群分。...GN算法是用于社区发现的算法。全程是Girvan Newman,是两位作者的名字组合。 该算法的大致思路是:
  • 基于GN算法的微博社区发现方法,韦庆杰,李京腾,随着互联网和移动通信技术的快速发展,微博已成为主流的在线社交网络平台。微博网络不只是简单的拓扑结构网络,它还包含信息交互
  • 社区发现GN算法 采用python编程加以实现 可直接运行。资源很好,有分的尽量下载一下。
  • rigraph实现边介数社区发现算法(GN)
  • 经典的GN算法

    2014-12-12 22:12:15
    很经典的社区划分算法,输出的内容比较明了

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,274
精华内容 2,509
关键字:

GN算法