http://blog.csdn.net/pipisorry/article/details/54020333

Networks算法Algorithms

最短路径Shortest Paths

shortest_path

all_shortest_paths

shortest_path_length

average_shortest_path_length

简单路径Simple Paths

`all_simple_paths`(G, source, target[, cutoff])	Generate all simple paths in the graph G from source to target.
`shortest_simple_paths`(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 Analysis

PageRank Hits

[Link Analysis]

链接预测Link Prediction

链接预测算法

`resource_allocation_index`(G[, ebunch])	Compute the resource allocation index of all node pairs in ebunch.
`jaccard_coefficient`(G[, ebunch])	Compute the Jaccard coefficient of all node pairs in ebunch.
`adamic_adar_index`(G[, ebunch])	Compute the Adamic-Adar index of all node pairs in ebunch.
`preferential_attachment`(G[, ebunch])	Compute the preferential attachment score of all node pairs in ebunch.
`cn_soundarajan_hopcroft`(G[, ebunch, community])	Count the number of common neighbors of all node pairs in ebunch using community information.
`ra_index_soundarajan_hopcroft`(G[, ebunch, ...])	Compute the resource allocation index of all node pairs in ebunch using community information.
`within_inter_cluster`(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)

[Link Prediction]

组件Components

connectivity连通性

连通子图Connected components

`is_connected`(G)	Return True if the graph is connected, false otherwise.
`number_connected_components`(G)	Return the number of connected components.
`connected_components`(G)	Generate connected components.
`connected_component_subgraphs`(G[, copy])	Generate connected components as subgraphs.
`node_connected_component`(G, n)	Return the nodes in the component of graph containing node n.

连通子图计算示例

from networkx.algorithms import traversal, componentsweighted_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])