将Networkx中的voterank算法改写为igraph形式
尝试将networkx中的voterank算法用igraph自定义函数调用
首先，需要贴出networkx中的voterank源码：
def voterank(G, number_of_nodes=None):
"""Select a list of influential nodes in a graph using VoteRank algorithm
VoteRank [1]_ computes a ranking of the nodes in a graph G based on a
voting scheme. With VoteRank, all nodes vote for each of its in-neighbours
and the node with the highest votes is elected iteratively. The voting
ability of out-neighbors of elected nodes is decreased in subsequent turns.
Note: We treat each edge independently in case of multigraphs.
Parameters
----------
G : graph
A NetworkX graph.
number_of_nodes : integer, optional
Number of ranked nodes to extract (default all nodes).
Returns
-------
voterank : list
Ordered list of computed seeds.
Only nodes with positive number of votes are returned.
References
----------
.. [1] Zhang, J.-X. et al. (2016).
Identifying a set of influential spreaders in complex networks.
Sci. Rep. 6, 27823; doi: 10.1038/srep27823.
"""
influential_nodes = []
voterank = {}
if len(G) == 0:
return influential_nodes
if number_of_nodes is None or number_of_nodes > len(G):
number_of_nodes = len(G)
if G.is_directed():
# For directed graphs compute average out-degree
avgDegree = sum(deg for _, deg in G.out_degree()) / len(G)
else:
# For undirected graphs compute average degree
avgDegree = sum(deg for _, deg in G.degree()) / len(G)
# step 1 - initiate all nodes to (0,1) (score, voting ability)
for n in G.nodes():
voterank[n] = [0, 1]
# Repeat steps 1b to 4 until num_seeds are elected.
for _ in range(number_of_nodes):
# step 1b - reset rank
for n in G.nodes():
voterank[n][0] = 0
# step 2 - vote
for n, nbr in G.edges():
# In directed graphs nodes only vote for their in-neighbors
voterank[n][0] += voterank[nbr][1]
if not G.is_directed():
voterank[nbr][0] += voterank[n][1]
for n in influential_nodes:
voterank[n][0] = 0
# step 3 - select top node
n = max(G.nodes, key=lambda x: voterank[x][0])
if voterank[n][0] == 0:
return influential_nodes
influential_nodes.append(n)
# weaken the selected node
voterank[n] = [0, 0]
# step 4 - update voterank properties
for _, nbr in G.edges(n):
voterank[nbr][1] -= 1 / avgDegree
voterank[nbr][1] = max(voterank[nbr][1], 0)
return influential_nodes
改为igraph的voterank算法
def votrank_ig(G,number_of_nodes = None):
'''
using igraph to rewrite voterank
'''
influential_nodes = []
voterank = {}
if number_of_nodes is None or number_of_nodes > len(G.vs()):
number_of_nodes = len(G.vs())
if G.is_directed():
# For directed graphs compute average out-degree
avgDegree = sum(deg.outdegree() for deg in G.vs()) / len(G.vs())
else:
# For undirected graphs compute average degree
avgDegree = sum(deg.outdegree() for deg in G.vs()) / len(G.vs())
# step1
for n in range(len(G.vs())):
voterank[n] = [0, 1]
for _ in range(number_of_nodes):
# step 1b - reset rank
for n in G.vs():
voterank[n["id"]][0] = 0
# step 2 - vote
for e in G.es:
# In directed graphs nodes only vote for their in-neighbors
v1, v2 = e.source, e.target
voterank[v1][0] += voterank[v2][1]
if not G.is_directed():
voterank[v2][0] += voterank[v1][1]
for n in influential_nodes:
voterank[n][0] = 0
# step 3 - select top node
n = max(G.vs["id"], key=lambda x: voterank[x][0])
if voterank[n][0] == 0:
return influential_nodes
influential_nodes.append(n)
# weaken the selected node
voterank[n] = [0, 0]
# step 4 - update voterank properties
for e in (G.vs[n]).incident():
nbr = e.target
voterank[nbr][1] -= 1 / avgDegree
voterank[nbr][1] = max(voterank[nbr][1], 0)
return influential_nodes
跑实验对比：
（1）Networkx 写法
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
G = nx.DiGraph()
Matrix = np.array([
[0,1,1,1,1,1,1,1,1,1],
[0,0,1,1,1,1,1,1,0,1],
[0,0,0,1,1,1,1,0,1,1],
[0,0,0,0,0,0,1,1,1,1],
[0,0,0,0,0,0,1,1,1,1],
[0,0,0,0,0,0,1,1,1,1],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,1,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0]
])
for i in range(len(Matrix)):
for j in range(len(Matrix)):
if Matrix[i][j]:
G.add_edge(i,j)
pos = nx.circular_layout(G)
nx.draw(G,pos,with_labels=True)
print(voterank(G))
结果为： [0, 1, 2, 3, 4]
（2）igraph写法
from igraph import *
g = Graph(directed=True)
g.add_vertices(10)
# add ids and labels to vertices
for i in range(len(g.vs)):
g.vs[i]['id'] = i
g.vs[i]['label'] = str(i)
g.add_edges([(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(1,2),(1,3),
(1,4),(1,5),(1,6),(1,7),(1,9),(2,3),(2,4),(2,5),(2,6),(2,8),(2,9),
(3,6),(3,7),(3,8),(3,9),(4,6),(4,7),(4,8),(4,9),(5,6),(5,7),(5,8),
(5,9),(7,8)])
# 设置可视化类型，并使用可视化类型
visual_style = {}
visual_style['vertex_size'] = 45
visual_style['vertex_color'] = 'white'
visual_style['vertex_label_size'] = 22
visual_style['layout'] = g.layout_circle()
visual_style['bbox'] = (400,400)
visual_style['margin'] = 27
plot(g, 'graph.png',**visual_style)```
print(votrank_ig(g))
结果仍是： [0, 1, 2, 3, 4]
因此，该函数改写成功！可以直接复制调用了。
[1]: https://networkx.org/documentation/stable/_modules/networkx/algorithms/centrality/voterank_alg.html#voterank
[2]: https://www.centiserver.org/centrality/VoteRank/