复杂网络社区结构发现算法-基于python networkx clique渗透算法_a_step_further的博客

clique渗透算法简介

对于一个图G而言，如果其中有一个完全子图（任意两个节点之间均存在边），节点数是k，那么这个完全子图就可称为一个k-clique。

进而，如果两个k-clique之间存在k-1个共同的节点，那么就称这两个clique是“相邻”的。彼此相邻的这样一串clique构成最大集合，就可以称为一个社区（而且这样的社区是可以重叠的，即所谓的overlapping community，就是说有些节点可以同时属于多个社区）。下面第一组图表示两个3-clique形成了一个社区，第二组图是一个重叠社区的示意图。

networkx中实现的clique渗透算法接口如下：

找社区（上代码）

以无向无权图为示例

#!/usr/bin/python
#coding:utf-8
import sys
import networkx as nx
import time
def find_community(graph,k):
    return list(nx.k_clique_communities(graph,k))
if __name__ == '__main__':
    if len(sys.argv) < 2:
        print "Usage: %s <InputEdgeListFile>" % sys.argv[0]
        sys.exit(1)
    #创建一个无向、无权图
    edge_list_file = sys.argv[1]
    wbNetwork = nx.read_edgelist(edge_list_file,delimiter='\t')
    print "图的节点数：%d" % wbNetwork.number_of_nodes()
    print "图的边数：%d" % wbNetwork.number_of_edges()
    #调用kclique社区算法
    for k in xrange(3,6):
        print "############# k值: %d ################" % k
        start_time = time.clock()
        rst_com = find_community(wbNetwork,k)
        end_time = time.clock()
        print "计算耗时(秒)：%.3f" % (end_time-start_time)
        print "生成的社区数：%d" % len(rst_com)

算法输出及讨论

单机64G内存的机器上测试了几个不同规模的网络，相应的输出如下：

可见该算法在单机上适合于计算10万以下节点中小规模网络社区结构。对于大规模的社交网络，必须要用分布式集群才行啊。

复杂网络 在现代科学中具有极为重要的地位，它被广泛应用于社会、生物、物理、化学等领域。本文将介绍如何使用 Python 语言实现 复杂网络 的构建、可视化和分析。我们可以使用 Python 中的 networkx 库来构建 复杂网络 。聚类系数是指网络中一个节点的邻居节点之间已经形成了多少条边。最短路径是指从一个节点到另一个节点的最短路径长度。度分布是指每个节点的度数在整个网络中出现的频率。我们可以使用 networkx 库来对 复杂网络 进行各种分析。我们可以使用matplotlib库来绘制 复杂网络 。 problem： Prove that the following problem is NP-complete:given an undirected graph G=(V,E) and an integer k, return a cli que of size k as well as an independent set of size k,provided both exist. 本人因为研究（谈不上研究，就是借鉴大佬们的方法）的是这个方向，发现使用 python 的不是很多，而且有些比较模糊，本人就自己的理解，分析在学习这个途中遇到的一些问题以及解决的办法，希望对你们有帮助，码字不易，顺带点个赞呗~ author：xiao黄缓慢而坚定的生长安装 networkx 这里就不过多讲述了，可以参考我的一篇博客。传送门 import networkx as nx... 前言最近因为业务数据分析的需要，看社区发现相关的东东稍多些，刚刚写过一篇基于igraph C library的方法(http://km.oa.com/group/22323/articles/show/240332)，然后想用k cli que 衍生的 cli que 渗透算法时发现 igraphC library 并未提供现成的api，对于懒人来说，这很不幸。既而发现 networkx 这个 python 包中是有的... 一、社区发现概述根据图论，加权网络表示为𝐺=(𝑉,𝐸,𝑊)，未加权网络表示为𝐺=(𝑉,𝐸)，其中𝑉和𝐸表示节点和边的集合，𝑊分别表示𝐸相应的权重，以连接的强度或容量为单位。在未加权的网络中，𝑊被视为1。子图𝑔⊆𝐺是保留原始网络结构的图划分。子图的划分遵循预定义（pre-define）的规则，不同的规则可能会导致不同形式的子图。社区是代表真实社会现象的一种子图。换句话说，社区是一组具有共同特征的人或对象。一、总体概述目前针对图网络结构，比较热门的一个部分就是知识图谱，知识图谱是基于二元关系知识库，构成网络结构，基本组成单位是”实体-关系-实体“的三元组，实体之间通过关系相互联结。主要可以应用的场景有：风险预测、反欺诈、精准营销、智能搜索等常用的是采用个人信息进行一个场景构建，构建知识图谱的流程例子如下所示: 1、通过对数据进行清理，抽取，构建知识图谱的节点，比如：姓名、ip、... 算法是以供水管网数据为例，后面给出了社区发现结果评价指标，模块度的计算结果。如有代码疑问，私聊即可。注：代码本人手写，未考虑任何效率问题，只是将算法过程实现，关于算法的介绍需要自行查看。 SCAN 算法中重要的两个参数为密度阈值（对标DBSCAN中的min_pts），节点结构相似度阈值（对标DBSCAN的邻域半径）。其中节点结构相似度阈值范围【0，1】，密度阈值最好大于等于2。 import wntr as wr from plotly import * import networkx as nx 团（ cli que ）：一个无向图的子图，该子图中所有任意两个顶点之间都存在一条边。极大团（maximal cli que ）：是一个团，该团不能被更大的团所包含，换句话说，再也不存在一个点能加入这个团。最大团（maximum cli que ）：是指一个图中size最大的极大团。团的size是指极大团的顶点个数。模块度用来衡量一个网络切分的好坏。 It was designed to measure the strength of division of. k- cli que .：是G的k个顶点的集合，使得每对顶点都有一条边。 k-ECC. A k-ECC (k-edge connected component)：G的一个子图，在去掉任何k–1边后，它仍然是连通的。