python复杂网络库networkx：算法

短命女 2022-07-13 09:37 235阅读 0赞

http://[blog.csdn.net/pipisorry/article/details/54020333][blog.csdn.net_pipisorry_article_details_54020333]

# Networks算法Algorithms #

## 最短路径Shortest Paths ##

[shortest\_path][shortest_path][  
][Link 1]

[all\_shortest\_paths][Link 1][  
][Link 2]

[shortest\_path\_length][Link 2][  
][Link 3]

[average\_shortest\_path\_length][Link 3][  
][Link 4]

[has\_path][Link 4][  
][Link 5]

[Advanced Interface][Link 5][  
][Link 6]

[Dense Graphs][Link 6][  
][Link 7]

[A\* Algorithm][Link 7]

\[[Shortest Paths][]\]

## 简单路径Simple Paths ##

<table> 
 <tbody> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/stable/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html#networkx.algorithms.simple_paths.all_simple_paths" title="networkx.algorithms.simple_paths.all_simple_paths" rel="nofollow"><code><span>all_simple_paths</span></code></a>(G,&nbsp;source,&nbsp;target[,&nbsp;cutoff])</td> 
   <td>Generate all simple paths in the graph G from source to target.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/stable/reference/generated/networkx.algorithms.simple_paths.shortest_simple_paths.html#networkx.algorithms.simple_paths.shortest_simple_paths" title="networkx.algorithms.simple_paths.shortest_simple_paths" rel="nofollow"><code><span>shortest_simple_paths</span></code></a>(G,&nbsp;source,&nbsp;target[,&nbsp;...])</td> 
   <td>Generate all simple paths in the graph G from source to target, starting from shortest ones.</td> 
  </tr> 
 </tbody> 
</table>

Note:nx.all\_simple\_paths只能迭代一次。

## 链接分析Link Analysis ##

PageRank Hits

\[[Link Analysis][]\]

## 链接预测Link Prediction ##

### 链接预测算法 ###

<table> 
 <tbody> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.link_prediction.resource_allocation_index.html#networkx.algorithms.link_prediction.resource_allocation_index" title="networkx.algorithms.link_prediction.resource_allocation_index" rel="nofollow"><code><span>resource_allocation_index</span></code></a>(G[,&nbsp;ebunch])</td> 
   <td>Compute the resource allocation index of all node pairs in ebunch.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.link_prediction.jaccard_coefficient.html#networkx.algorithms.link_prediction.jaccard_coefficient" title="networkx.algorithms.link_prediction.jaccard_coefficient" rel="nofollow"><code><span>jaccard_coefficient</span></code></a>(G[,&nbsp;ebunch])</td> 
   <td>Compute the Jaccard coefficient of all node pairs in ebunch.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.link_prediction.adamic_adar_index.html#networkx.algorithms.link_prediction.adamic_adar_index" title="networkx.algorithms.link_prediction.adamic_adar_index" rel="nofollow"><code><span>adamic_adar_index</span></code></a>(G[,&nbsp;ebunch])</td> 
   <td>Compute the Adamic-Adar index of all node pairs in ebunch.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.link_prediction.preferential_attachment.html#networkx.algorithms.link_prediction.preferential_attachment" title="networkx.algorithms.link_prediction.preferential_attachment" rel="nofollow"><code><span>preferential_attachment</span></code></a>(G[,&nbsp;ebunch])</td> 
   <td>Compute the preferential attachment score of all node pairs in ebunch.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.link_prediction.cn_soundarajan_hopcroft.html#networkx.algorithms.link_prediction.cn_soundarajan_hopcroft" title="networkx.algorithms.link_prediction.cn_soundarajan_hopcroft" rel="nofollow"><code><span>cn_soundarajan_hopcroft</span></code></a>(G[,&nbsp;ebunch,&nbsp;community])</td> 
   <td>Count the number of common neighbors of all node pairs in ebunch using community information.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.link_prediction.ra_index_soundarajan_hopcroft.html#networkx.algorithms.link_prediction.ra_index_soundarajan_hopcroft" title="networkx.algorithms.link_prediction.ra_index_soundarajan_hopcroft" rel="nofollow"><code><span>ra_index_soundarajan_hopcroft</span></code></a>(G[,&nbsp;ebunch,&nbsp;...])</td> 
   <td>Compute the resource allocation index of all node pairs in ebunch using community information.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.link_prediction.within_inter_cluster.html#networkx.algorithms.link_prediction.within_inter_cluster" title="networkx.algorithms.link_prediction.within_inter_cluster" rel="nofollow"><code><span>within_inter_cluster</span></code></a>(G[,&nbsp;ebunch,&nbsp;delta,&nbsp;...])</td> 
   <td>Compute the ratio of within- and inter-cluster common neighbors of all node pairs in ebunch.</td> 
  </tr> 
 </tbody> 
</table>

--------------------

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)

\[[Link Prediction][]\]

## 组件Components ##

### connectivity连通性 ###

连通子图Connected components

<table>     
 <tbody> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.components.connected.is_connected.html#networkx.algorithms.components.connected.is_connected" title="networkx.algorithms.components.connected.is_connected" rel="nofollow"><code><span>is_connected</span></code></a>(G)</td> 
   <td>Return True if the graph is connected, false otherwise.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.components.connected.number_connected_components.html#networkx.algorithms.components.connected.number_connected_components" title="networkx.algorithms.components.connected.number_connected_components" rel="nofollow"><code><span>number_connected_components</span></code></a>(G)</td> 
   <td>Return the number of connected components.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.components.connected.connected_components.html#networkx.algorithms.components.connected.connected_components" title="networkx.algorithms.components.connected.connected_components" rel="nofollow"><code><span>connected_components</span></code></a>(G)</td> 
   <td>Generate connected components.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.components.connected.connected_component_subgraphs.html#networkx.algorithms.components.connected.connected_component_subgraphs" title="networkx.algorithms.components.connected.connected_component_subgraphs" rel="nofollow"><code><span>connected_component_subgraphs</span></code></a>(G[,&nbsp;copy])</td> 
   <td>Generate connected components as subgraphs.</td> 
  </tr> 
  <tr> 
   <td><a href="http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.components.connected.node_connected_component.html#networkx.algorithms.components.connected.node_connected_component" title="networkx.algorithms.components.connected.node_connected_component" rel="nofollow"><code><span>node_connected_component</span></code></a>(G,&nbsp;n)</td> 
   <td>Return the nodes in the component of graph containing node n.</td> 
  </tr> 
 </tbody> 
</table>

连通子图计算示例

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 connectivity

Weak connectivity

Attracting components

Biconnected components

Semiconnectedness

\[[Components][]\]

## Connectivity ##

Connectivity and cut algorithms

\[ [Connectivity][]\]

## 遍历Traversal ##

深度优先遍历

\[[Depth First Search][]\]

广度优先遍历

\[[Breadth First Search][]\]

边的深度优先遍历

\[[Depth First Search on Edges][]\]

\[[Traversal][]\]

[皮皮blog][blog]

## networkx算法示例    ##

### 使用networkx计算所有路径及路径距离    ###

\[[jupyter][]\]

\[[python—networkx：求图的平均路径长度并画出直方图][python_networkx]\]

### 社区发现 ###

\[[复杂网络社区结构发现算法-基于python networkx clique渗透算法][-_python networkx clique] \]

[皮皮blog][blog]

from: [http://blog.csdn.net/pipisorry/article/details/54020333][blog.csdn.net_pipisorry_article_details_54020333]

ref: \[[Algorithms][]\]

\[[Networkx Reference][]\]\*\[[NetworkX documentation][]\]\*\[[doc NetworkX Examples][]\]\*\[[NetworkX Home][]\]

[blog.csdn.net_pipisorry_article_details_54020333]: http://blog.csdn.net/pipisorry/article/details/54020333
[shortest_path]: http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html
[Link 1]: http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.shortest_paths.generic.all_shortest_paths.html
[Link 2]: http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.shortest_paths.generic.shortest_path_length.html
[Link 3]: http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.shortest_paths.generic.average_shortest_path_length.html
[Link 4]: http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.shortest_paths.generic.has_path.html
[Link 5]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.shortest_paths.html#module-networkx.algorithms.shortest_paths.unweighted
[Link 6]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.shortest_paths.html#module-networkx.algorithms.shortest_paths.dense
[Link 7]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.shortest_paths.html#module-networkx.algorithms.shortest_paths.astar
[Shortest Paths]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.shortest_paths.html
[Link Analysis]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.link_analysis.html
[Link Prediction]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.link_prediction.html
[Components]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.component.html
[Connectivity]: http://networkx.readthedocs.io/en/stable/reference/algorithms.connectivity.html
[Depth First Search]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.traversal.html#module-networkx.algorithms.traversal.depth_first_search
[Breadth First Search]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.traversal.html#module-networkx.algorithms.traversal.breadth_first_search
[Depth First Search on Edges]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.traversal.html#module-networkx.algorithms.traversal.edgedfs
[Traversal]: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.traversal.html
[blog]: http://blog.csdn.net/pipisorry
[jupyter]: http://nbviewer.jupyter.org/gist/anonymous/7084321
[python_networkx]: http://blog.csdn.net/ztf312/article/details/47663209
[-_python networkx clique]: http://www.codexiu.cn/python/blog/10334/
[Algorithms]: http://networkx.readthedocs.io/en/stable/reference/algorithms.html
[Networkx Reference]: http://networkx.readthedocs.io/en/networkx-1.11/reference/index.html
[NetworkX documentation]: http://networkx.github.io/documentation/latest/index.html
[doc NetworkX Examples]: http://networkx.readthedocs.io/en/stable/examples/index.html
[NetworkX Home]: https://networkx.github.io/#