在做东西的时候用到了社区发现，因此了解了一下有关社区发现的一些问题
1，社区发现算法
（1）SCAN：一种基于密度的社团发现算法
&Paper: 《SCAN: A Structural Clustering Algorithm for Networks》 &Auther: Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, Thomas A. J. Schweiger &Conference: SIGKDD 2007& &
主要概念：
节点相似度定义为两个节点共同邻居的数目与两个节点邻居数目的几何平均数的比值（这里的邻居均包含节点自身）。
节点的 ? - 邻居定义为与其相似度不小于 ? 的节点所组成的集合
核节点是指 ? 邻居的数目大于 μ 的节点。
节点 w 是核节点 v 的 ? 邻居，那么称从 v 直接可达 w.&
节点 v 可达 w ，当且仅当存在一个节点链 v1,…,vn∈V,v1=v,vn=w,使得 vi+1 是 从vi 直接可达的。
若核节点u可达节点v和节点w，则称节点v和节点w相连.
具体算法：
对于每个未分配社团的节点 v ，检查 v 是否是核节点，是核节点则将其直接可达节点分配到一个社团中（社团标号记为该节点），并将其?-邻居放进队列中，重复进行1步骤（类似于对直接可达节点进行DFS）。
若 v 不是核节点则将其标志为non-member。
最后检查所有的non-menber节点，若其相邻节点存在于两个及以上的社团中，则将其标为hub节点，否则标为outlier。
ALGORITHM SCAN(G=&V, E&, ε, μ)
// all vertices in V are lab
for each unclassified vertex v ∈ V do
// STEP 1. check
if COREε,μ(v) then
// STEP 2.1. if v is a core, a new
generate new clusterID;
insert all x ∈ Nε (v) into queue Q;
while Q ≠ <span style="color: # do
y = first vertex in Q;
R = {x ∈ V | DirREACHε,μ(y, x)};
for each x ∈ R do
if x is unclassified or non-member then
assign current clusterID
if x is unclassified then
insert x into queue Q;
remove y from Q;
// STEP 2.2. if v is not a core, it is labeled as non-member
label v as non-
// STEP 3. further classifies non-members
for each non-member vertex v do
if (? x, y ∈ Γ(v) ( x.clusterID ≠ y.clusterID) then
label v as hub
label v as
(2)复杂网络社区结构发现算法-基于python networkx clique渗透算法
Paper:&G. Palla, I. Derényi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature, vol. 435, pp. 814-818, 2005.
clique渗透算法简介:
& &&对于一个图G而言，如果其中有一个完全子图（任意两个节点之间均存在边），节点数是k，那么这个完全子图就可称为一个k-clique。
& & 进而，如果两个k-clique之间存在k-1个共同的节点，那么就称这两个clique是“相邻”的。彼此相邻的这样一串clique构成最大集合，就可以称为一个社区（而且这样的社区是可以重叠的，即所谓的overlapping community，就是说有些节点可以同时属于多个社区）。下面第一组图表示两个3-clique形成了一个社区，第二组图是一个重叠社区的示意图。
2.NetWorkX安装使用和示例
NetworkX是一个用Python语言开发的图论与复杂网络建模工具，内置了常用的图与复杂网络分析算法，可以方便的进行复杂网络数据分析、仿真建模等工作。这里主要介绍clique渗透算法，
首先是软件的下载地址，&https://pypi.python.org/pypi/networkx/，我下载的是whl文件
接着就是安装whl文件，具体安装过程网上有好多可以参考这个 ，
接着安转完就是看如何执行算法了，我使用了pycharm IDE，我执行的是clique渗透算法，下边是这个算法的主要实现
"""Find k-clique communities in graph using the percolation method.A k-clique community is the union of all cliques of size k that can be reached through adjacent (sharing k-1 nodes) k-cliques.Parameters:
k (int) – Size of smallest clique
cliques (list or generator) – Precomputed cliques (use networkx.find_cliques(G))Return type:Yields sets of nodes, one for each k-clique community.
"""import networkx as nx
import sys
import time
def find_community(graph,k):
return list(nx.k_clique_communities(graph,k))
G = nx.Graph()
##testFile=open("F://2.txt","r") ##2-6
testFile=open("F://21.txt","r") ##5,10
for line in testFile:
a=line.strip('\n').split(",")
G.add_edge(a[0],a[1])
for k in range(5,10):
print ("############# k值: %d ################" % k)
start_time = time.clock()
rst_com = find_community(G,k)
end_time = time.clock()
print ("计算耗时(秒)：%.3f" % (end_time-start_time))
print ("生成的社区数：%d" % len(rst_com))
print(rst_com)
其中文件的格式是
Gephi是一款开源免费跨平台基于JVM的复杂网络分析软件, 其主要用于各种网络和复杂系统，动态和分层图的交互可视化与探测开源工具。
gephi.org， 可在官网上免费下载此软件。
目前gephi已有中文教程，网址为：/gephi 。
参考文献：
阅读(...) 评论()数据挖掘（1）
python（28）
创建简单的空图形（没有边和点）
&&&&import networkx as nx
& & g = nx.Graph();
& & h = nx.Graph( g); & &#可以在构建Graph对象时指定值来构造一个新的Graph对象
& & f = nx.Graph( [ (1,2),(2,3),(1,3)]); &#可以在构建Graph对象时指定node关系的数组来构建Graph对象
&&&&根据定义，一个Graph就是一个所有nodes的集合。在NetworkX中，nodes能够代表任何对象，例如一个文本，一个图片，一个xml对象或者另外一个Graph，一个自定义的对象等等。
& & 由于NetworkX提供了多种Graph对象生成方法，并且体痛了读写方法来读写多种格式，所以Graph对象能够使用多种方式创建。
----------------------
& & graph对象能够添加node（节点）
& & g.add_node(1); & #添加一个节点&&&&
& & g.add_nodes_from( [2,3]) & #添加一个节点列表
& & h =&nx.path_graph(10)
&&&&g.add_nodes_from( h) &#添加一个能够迭代的集合(例如：list, set, graph, file等等)，这样g中包含了h中的元素
& & g.add_node( h) & &#这是将h作为一个node添加到g中
& & g.add_nodes_from( 'span'); & #将span拆分为一个字符数组，然后添加node
& & Note: 最后，h是一个graph对象，将h最为g的node，是一个很灵活的特性。这样节点可以是graph中的graph，files中的graphs，method中的graph等等。值得思考的是，如果结构化你的应用使得那些node都是有用的实体。如果你愿意，你还可以是g对应一个唯一的表示，每个node对应一个被表示的key。如果node对应的是对象中的内容，那么当内容变化是，不应该修改对象，应该修改node对应的内容（有点绕）。
-----------------------
& & graph对象中还能够添加edges(边)；
& & g.add_edge(1,2) & &# 添加一个1和2之间的edge
& & e=(2,3) & & & & & & & & & #定义个关系
& & g.add_edge( *e) & &#添加关系对象
& & g.add_edges_from([(1,2),(2,3)]) &#添加一个edge数组
& & g.add_edges_from( h.edges()); & #h.edges()返回的h的包含所有edge的数组
& & #拆除graph对象中的node和edge可以使用如下方法
& & g.remove_node()
& & g.remove_nodes_from()
& & g.remove_edge()
& & g.remove_edges_from()
& & #删除所有的node和edge
& & g.clear();
& & #如果重复添加相同的node和edge，NetworkX将会将会忽略那些重复的内容。
& & g.add_nodes_from(&span&);
& & g.add_node( &s&);
& & #获取一个Graph对象中node和edge的数量
& & g.number_of_nodes();
& & g.number_of_edges();
& & #获取一个Graph对象中的node数组或者edge数组
& & g.nodes();
& & g.edges();
& & g.neighbors(1); & #获取与node为1相邻的node是节点
& & g.remove_edge( 1,2); & #删除node1和node2之间的edge，自此node1和node2不再为相邻的node
------------------------------
如何使用nodes和edges？
& & 获取你已经注意到了node和edge并不是Graph的对象。这就能够使你更加灵活的使用node和edge，如果在python中使用string和number。node可以为任何hashable对象（除了Node），edge还可以和其他Graph对象中的node建立关联。例如：
&&&&& & g.add_node( n1, n2, Graph=x);
&&&&& & 例如，n1,n2可以代表生物蛋白质资料库中两种蛋白质对象,x可以是代表一个观察实验出版物中的xml片段记录。
&&&&& & 如果熟悉他们，那么他们会非常有用。如果滥用也会带来意想不到的结果。如有疑问可以通过convert_node_labels_to_integers()方法来获得更多的有整数组成的传统图形。
-------------------------
除了使用上面提到的方法外，可以使用索引下标来访问edge
& & &&&g[1]
& & {2,{}}
& & &&&g[1][1]
& & Note：不要修改返回到额字典结构，它是graph固有的一部分，直接修改会导致不一致的状态
& & 同样通过下标可以设置edge的属性
& & g.add_edge( 1, 3)
& & g[1][1][ &color&] = &blue&
& & 通过迭代快速查找所有的edge
&&& FG=nx.Graph()
&&& FG.add_weighted_edges_from([(<span class="mi" style="color:#,<span class="mi" style="color:#,<span class="mf" style="color:#.125),(<span class="mi" style="color:#,<span class="mi" style="color:#,<span class="mf" style="color:#.75),(<span class="mi" style="color:#,<span class="mi" style="color:#,<span class="mf" style="color:#.2),(<span class="mi" style="color:#,<span class="mi" style="color:#,<span class="mf" style="color:#.375)])
&&& for n,nbrs in FG.adjacency_iter():
for nbr,eattr in nbrs.items():
data=eattr['weight']
if data&<span class="mf" style="color:#.5: print('(%d, %d, %.3f)' % (n,nbr,data))
(1, 2, 0.125)
(2, 1, 0.125)
(3, 4, 0.375)
(4, 3, 0.375)
--------------------
添加graph，node，edge的属性
&&&&& & 像color,label,weight或者其他Python对象的属性都可以被设置为graph，node，edge的属性。
&&&&& & 每个graph，node，edge都能够包含key/value这样的字典数据。默认情况下是没有这些属性的。可以通过add_node(),add_edge(),或者直接修改来添加和修改属性。
&&&&& &&Graph 属性
&&&&&&&&&&&&
&&&&&&&&& & g = nx.Graph( day=&friday&);
&&&&&&&&& & g.graph
&&&&&&&&& & 打印：｛“day”：“friday”｝
&&&&&&&&& & g.graph[&day&]=&Monday&;
&&&&&&&&& & g.graph
&&&&&&&&& & 打印：｛&day&:&Monday&｝
&&&&& &&Node属性
&&&&&&&&& & 通过add_node()，add_nodes_from或者g.node来添加属性
&&&&&&&&& & g.add_node( 1, time=&5pm&);
&&&&&&&&& & g.add_nodes_from([3], time=&2pm&);
&&&&&&&&& & g.node[ 1]
&&&&&&&&& & 打印：｛&time&:&5pm&｝
&&&&&&&&& & g.node[1][&room&]=714;
&&&&&&&&& & g.nodes(data=True);
&&&&&&&&& & 打印：[(1,{&room&:714, &time&:&5pm&}),(3,{&time&:&2pm&})]
&&&&&&&&& & Note:向node添加属性并不会想graph添加属性，
&&&&& &&Edge属性
&&&&&&&&& & 通过add_edge(), add_edges_from()或者g.edge来添加属性
&&&&&&&&& & g.add_edge(1,2,wegiht=4.7)
&&&&&&&&& & g.add_edges_from( [ (2,3),(3,4) ], color=&red&)
&&&&&&&&& & g.add_edges_from( [(1,2,{&color&:&blue&}),(4,5,{&weight&:8})])
&&&&&&&&& & g[1][2][&width&]=4.7
&&&&&&&&& & g.edge[1][2][&weight&]=4
-----------------------------
Directed graphs(有向图)
&&&&&&&&& & DiGraph类针对有向edge提供了另外的方法，例如：out_edges(), in_degree(),predecessors(),successors()等。为了是算法能够正常运行，有向版本的neighbors()和degree()对于seccessor()方法是相同的。in_degree()和out_degree()都是独自的。
&&&&&&&&&&&&
&&&&&&&&& & ig = nx.DiGraph()
&&&&&&&&& & ig.add_wieghted_edges_from( [(1,2,0.5),(2,3,0.7)])
&&&&&&&&& & ig.out_degree( 1,weight=&weight&);
&&&&&&&&& & 打印：0.5
&&&&&&&&& & ig.degree( 1, weight=&weight&);
&&&&&&&&& & 打印：1.25
&&&&&&&&& & ig.seccessors(1)
&&&&&&&&& & 打印:[2]
&&&&&&&&& & ig.neighbors(1)
&&&&&&&&& & 打印:[2]
&&&&& & 一些算法只对有向grapsh起作用，其他算法没有明确定义。同时使用有向graph和无向graph是非常危险的事情。如果想将有向graph转换为无向graph可以使用
&&&&&&&&&&&&Graph.to_undirected()
&&&&&&&&& & 或者
&&&&&&&&&&&&
&&&&&&&&& & h = nx.Graph( g)
-------------------
Multigraphs
&&&&&&&&& & NetworkX提供了类来实现一对node之间存在多个edge的实现类：MultiGraph和MultiDiGraph，他们都允许使用的edge数据添加多个的edge。对于某些应这个特性非常有用，但是很多算法在这种graph中并没有明确定义。
&&& MG=nx.MultiGraph()
&&& MG.add_weighted_edges_from([(<span class="mi" style="color:#,<span class="mi" style="color:#,.<span class="mi" style="color:#), (<span class="mi" style="color:#,<span class="mi" style="color:#,.<span class="mi" style="color:#), (<span class="mi" style="color:#,<span class="mi" style="color:#,.<span class="mi" style="color:#)])
&&& MG.degree(weight='weight')
{1: 1.25, 2: 1.75, 3: 0.5}
&&& GG=nx.Graph()
&&& for n,nbrs in MG.adjacency_iter():
for nbr,edict in nbrs.items():
minvalue=min([d['weight'] for d in edict.values()])
GG.add_edge(n,nbr, weight = minvalue)
&&& nx.shortest_path(GG,<span class="mi" style="color:#,<span class="mi" style="color:#)
---------------------
Graph generators and graph operations(图形生成和操作)
&&&&& & 为了构建node-by-node或者edge-by-edge的graph，还可以使用以下方式。
&&&&& & subgraph( G, nbunch)
&&&&& & union( g1,g2) & & & & & & & & #合并praph
&&&&& & disjoint_union( g1, g2) #假设所有node都不相同合并praph
&&&&& & cartesian_product( g1, g2) &#返回笛卡尔产品praph
&&&&& & compose( g1, g2) & & & & & & & & #合并公共的node
&&&&& & complement( g1) & & & & & & & & #praph的补集
&&&&& & create_empty_copy( g) & & & &#返回某个praph对象的空的拷贝对象
&&&&& & convert_to_undirected( g) & #返回一个无向praph
&&&&& & convert_to_directed( g) & & & #返回一个有向的praph
&&&&& & 使用小图的调用
&&&&& & petersen = nx.petersen_parph();
&&&&& & tutte = nx.tutte_praph()
&&&&& & maze = nx.sedgewick_maze_praph()
&&&&& & tet = nx.tetrahedral_praph()
&&&&& & 使用典型praph的构造生成器
&&&&& & k_4 = nx.complete_graph(4);
&&&&& & k_3_5 = nx.complete_bipartite_graph(3,5)
&&&&& & barbell = nx.barbell_graph( 10, 10)
&&&&& & lollipop = nx.lollipop_graph( 10,20);
&&&&& & 使用随机graph生成器
&&& er=nx.erdos_renyi_graph(<span class="mi" style="color:#0,<span class="mf" style="color:#.15)
&&& ws=nx.watts_strogatz_graph(<span class="mi" style="color:#,<span class="mi" style="color:#,<span class="mf" style="color:#.1)
&&& ba=nx.barabasi_albert_graph(<span class="mi" style="color:#0,<span class="mi" style="color:#)
&&& red=nx.random_lobster(<span class="mi" style="color:#0,<span class="mf" style="color:#.9,<span class="mf" style="color:#.9)
&&&&& & 从存储praph的文件中读取格式数据然后生成praph。
&&& nx.write_gml(red,&path.to.file&)
&&& mygraph=nx.read_gml(&path.to.file&)
--------------
Analyzing graphs(分析图)
& & 结构话的praph能够使用提供的方法来进行分析：
&&&&& & g = nx.Graph()
&&&&& & g.add_edges_from( [(1,2),(1,3)])
&&&&& & g.add_node( &spam&)
&&&&& & nx.connected_components( g) & #将node有关联的显示一个数组中。返回的为一个数组
&&&&& & 打印: [ [1,2,3], [ &spam&]]
&&&&& & sorted( nx.degree( g).values())
&&&&& & 打印： [ 0, 1, 1, 2]
&&&&& & nx.clustering( g) & #聚合
&&&&& & 打印： { 1 : 0.0, 2:0.0 , 3: 0.0 . &spam&:0.0}
&&&&& & nx.degree( g) & & & &#显示等级
&&&&& & 打印:{1:2, 2:1,3:1,&spam&:0}
&&&&& & 对于特殊的node，可以将一个单独的node或者node集合作为参数。如果传入一个独立的node，那么返回一个独立的值，如果传入一个node集合，这个方法将返回一个字典类型的数据&&&&
&&&&& & nx.degree(g,1)&&&&& & #返回第一个node的值
&&&&& & g.degree( 1) & & & & & #返回第一个node的值
&&&&& & g.degree( 1, 2) & & & #返回从第一个node开始，前两个node的值
&&&&& & {1:2, 2:1}
&&&&& & sorted( g.degree( [ 1, 2]).values()) &#返回1和2并排序输出结果
&&&&& & [1,2]
&&&&& & sorted( g.degree().values()) & & & & & &#返回g中node的权重，并排序输出结果
&&&&& & 想要了解更加详细的算法只是，参考：
---------------------
Drawing Praphs(绘制图形)
&&&&& & NetworkX并不是首选的图形绘制包，但是它包含了基本的图形绘制工具开源包Matplotlib。如果需要的话可以引入network.drawing包。（更详细的文档参考：）
&&&&& & 注意： NetworkX中的绘图包不和Python3兼容
&&&&& & 首先引入 Matplotlib的plot接口
&&&&& & import matplotlib.pyplot as plt
&&&&& & 如果成功引入 networkx.drawing那么可以使用下面的方法绘制graph对象
&&&&& & nx.draw( g)
&&&&& & nx.draw_random( g)
&&&&& & nx.draw_circular( g)
&&&&& & nx.draw_spectral( g)
&&&&& & 将绘制的内容保存的一个文件中使用下面的方法
&&&&& & nx.draw( g)
&&&&& & plt.savefig( &path.png&)
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：58044次
积分：3249
积分：3249
排名：第8510名
原创：237篇
转载：188篇
评论：11条
(8)(12)(4)(20)(45)(68)(42)(46)(70)(71)(40)(5)(6)networkx小记（1）
http://Networks算法Algorithms最短路径Shortest Paths[]简单路径Simple Paths(G,&source,&target[,&cutoff])Generate all simple paths in the graph G from source to target.(G,&source,&target[,&...])Generate all simple paths in the graph G from source to target,
starting from shortest ones.Note:nx.all_simple_paths只能迭代一次。链接分析Link AnalysisPageRank Hits[]链接预测Link Prediction链接预测算法(G[,&ebunch])Compute the resource allocation index of all node pairs in ebunch.(G[,&ebunch])Compute the Jaccard coefficient of all node pairs in ebunch.(G[,&ebunch])Compute the Adamic-Adar index of all node pairs in ebunch.(G[,&ebunch])Compute the preferential attachment score of all node pairs in ebunch.(G[,&ebunch,&community])Count the number of common neighbors of all node pairs in ebunch
using community information.(G[,&ebunch,&...])Compute the resource allocation index of all node pairs in ebunch using community information.(G[,&ebunch,&delta,&...])Compute the ratio of within- and inter-cluster common neighbors of all node pairs in ebunch.
Note: 返回的基本都是iterator of 3-tuples in the form (u, v, p)。iterator只能迭代一次，否则为空了。不指定ebunch的话就是计算所有没有边的点。If ebunchis None then all non-existent edges in the graph will be used.单纯cn个数的计算def commonNeighbor(G, ebunch=None):
compute num of common neighbor
import networkx as nx
if ebunch is None:
ebunch = nx.non_edges(G)
def predict(u, v):
cnbors = list(nx.common_neighbors(G, u, v))
return len(cnbors)
return ((u, v, predict(u, v)) for u, v in ebunch)[]组件Componentsconnectivity连通性连通子图Connected components(G)Return True if the graph is connected, false otherwise.(G)Return the number of connected components.(G)Generate connected components.(G[,©])Generate connected components as subgraphs.(G,&n)Return the nodes in the component of graph containing node n.连通子图计算示例from networkx.algorithms import traversal, components
weighted_edges = pd.read_csv(os.path.join(CWD, 'middlewares/network_reid.txt'), sep=',',
header=None).values.tolist()
g = nx.Graph()
g.add_weighted_edges_from(weighted_edges)
# print('#connected_components of g: {}'.format(nx.number_connected_components(g)))
component_subgs = components.connected_component_subgraphs(g)
for component_subg in component_subgs:
print(component_subg.nodes_list()[:5])Strong connectivityWeak connectivityAttracting componentsBiconnected componentsSemiconnectedness[]ConnectivityConnectivity and cut algorithms[]遍历Traversal深度优先遍历[]广度优先遍历[]边的深度优先遍历[][]networkx算法示例使用networkx计算所有路径及路径距离[][]社区发现[ ]from: ref: [][]*[]*[]*[]
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1152686次
积分：15637
积分：15637
排名：第538名
原创：499篇
转载：73篇
评论：141条
文章：21篇
阅读：66437
阅读：15450
文章：13篇
阅读：32197
阅读：19626
文章：16篇
阅读：56809
文章：18篇
阅读：35198
(5)(3)(15)(18)(18)(23)(4)(5)(16)(6)(11)(15)(5)(4)(5)(29)(8)(12)(9)(10)(16)(20)(19)(7)(24)(9)(15)(19)(57)(12)(28)(15)(36)(15)(19)(2)(2)
Contact me2147人阅读
语言系列：Python（69）
首先输入边和边的权重，随后画出节点位置，根据权重大小划分实边和虚边
#coding:utf-8
#!/usr/bin/env python
An example using Graph as a weighted network.
__author__ = &&&Aric Hagberg (hagberg@lanl.gov)&&&
import matplotlib.pyplot as plt
import networkx as nx
G=nx.Graph()
#添加带权边
G.add_edge('a','b',weight=0.6)
G.add_edge('a','c',weight=0.2)
G.add_edge('c','d',weight=0.1)
G.add_edge('c','e',weight=0.7)
G.add_edge('c','f',weight=0.9)
G.add_edge('a','d',weight=0.3)
#按权重划分为重权值得边和轻权值的边
elarge=[(u,v) for (u,v,d) in G.edges(data=True) if d['weight'] &0.5]
esmall=[(u,v) for (u,v,d) in G.edges(data=True) if d['weight'] &=0.5]
pos=nx.spring_layout(G) # positions for all nodes
#首先画出节点位置
nx.draw_networkx_nodes(G,pos,node_size=700)
#根据权重，实线为权值大的边，虚线为权值小的边
nx.draw_networkx_edges(G,pos,edgelist=elarge,
nx.draw_networkx_edges(G,pos,edgelist=esmall,
width=6,alpha=0.5,edge_color='b',style='dashed')
# labels标签定义
nx.draw_networkx_labels(G,pos,font_size=20,font_family='sans-serif')
plt.axis('off')
plt.savefig(&weighted_graph.png&) # save as png
plt.show() # display
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：133085次
积分：3239
积分：3239
排名：第8563名
原创：188篇
转载：25篇
译文：11篇
评论：40条
阅读：1556
(16)(4)(1)(7)(3)(2)(5)(31)(46)(1)(6)(2)(16)(7)(13)(43)(5)(2)(6)
