diff options
author | Mridul Seth <seth.mridul@gmail.com> | 2022-06-04 19:22:18 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-06-04 10:22:18 -0700 |
commit | ddb1cb663d1c0be293aaa4d4284eab641255014f (patch) | |
tree | c29df79558ae66b96e4edc8a58cdf2d162a835bb | |
parent | 0784e7b94c9cf706c566e17b0b2273c49f1573c5 (diff) | |
download | networkx-ddb1cb663d1c0be293aaa4d4284eab641255014f.tar.gz |
MAINT: Cleanup centrality module, remove unused variables (#5308)
* MAINT: Cleanup centrality module, remove unused variables
* make isort linter happy
* MAINT: make the loop more readable
Co-authored-by: Dan Schult <dschult@colgate.edu>
* make black happy
* Use a different name for internal function variable
Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com>
* rename closeness_cen to closeness_dict
* minor cleanup in current_flow_betweenness and group
Co-authored-by: Dan Schult <dschult@colgate.edu>
Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com>
18 files changed, 70 insertions, 82 deletions
diff --git a/networkx/algorithms/centrality/__init__.py b/networkx/algorithms/centrality/__init__.py index c15304c8..cf07fe22 100644 --- a/networkx/algorithms/centrality/__init__.py +++ b/networkx/algorithms/centrality/__init__.py @@ -1,10 +1,9 @@ from .betweenness import * from .betweenness_subset import * from .closeness import * -from .subgraph_alg import * -from .current_flow_closeness import * from .current_flow_betweenness import * from .current_flow_betweenness_subset import * +from .current_flow_closeness import * from .degree_alg import * from .dispersion import * from .eigenvector import * @@ -12,8 +11,9 @@ from .group import * from .harmonic import * from .katz import * from .load import * -from .reaching import * from .percolation import * +from .reaching import * from .second_order import * +from .subgraph_alg import * from .trophic import * from .voterank_alg import * diff --git a/networkx/algorithms/centrality/betweenness.py b/networkx/algorithms/centrality/betweenness.py index 87fd17e4..54b7db99 100644 --- a/networkx/algorithms/centrality/betweenness.py +++ b/networkx/algorithms/centrality/betweenness.py @@ -132,9 +132,9 @@ def betweenness_centrality( S, P, sigma, _ = _single_source_dijkstra_path_basic(G, s, weight) # accumulation if endpoints: - betweenness, delta = _accumulate_endpoints(betweenness, S, P, sigma, s) + betweenness, _ = _accumulate_endpoints(betweenness, S, P, sigma, s) else: - betweenness, delta = _accumulate_basic(betweenness, S, P, sigma, s) + betweenness, _ = _accumulate_basic(betweenness, S, P, sigma, s) # rescaling betweenness = _rescale( betweenness, diff --git a/networkx/algorithms/centrality/closeness.py b/networkx/algorithms/centrality/closeness.py index 1317f050..61af12c4 100644 --- a/networkx/algorithms/centrality/closeness.py +++ b/networkx/algorithms/centrality/closeness.py @@ -115,7 +115,7 @@ def closeness_centrality(G, u=None, distance=None, wf_improved=True): nodes = G.nodes else: nodes = [u] - closeness_centrality = {} + closeness_dict = {} for n in nodes: sp = path_length(G, n) totsp = sum(sp.values()) @@ -127,11 +127,10 @@ def closeness_centrality(G, u=None, distance=None, wf_improved=True): if wf_improved: s = (len(sp) - 1.0) / (len_G - 1) _closeness_centrality *= s - closeness_centrality[n] = _closeness_centrality + closeness_dict[n] = _closeness_centrality if u is not None: - return closeness_centrality[u] - else: - return closeness_centrality + return closeness_dict[u] + return closeness_dict @not_implemented_for("directed") @@ -252,10 +251,10 @@ def incremental_closeness_centrality( return nx.closeness_centrality(G) nodes = G.nodes() - closeness_centrality = {} + closeness_dict = {} for n in nodes: if n in du and n in dv and abs(du[n] - dv[n]) <= 1: - closeness_centrality[n] = prev_cc[n] + closeness_dict[n] = prev_cc[n] else: sp = path_length(G, n) totsp = sum(sp.values()) @@ -267,7 +266,7 @@ def incremental_closeness_centrality( if wf_improved: s = (len(sp) - 1.0) / (len_G - 1) _closeness_centrality *= s - closeness_centrality[n] = _closeness_centrality + closeness_dict[n] = _closeness_centrality # Leave the graph as we found it if insertion: @@ -275,4 +274,4 @@ def incremental_closeness_centrality( else: G.add_edge(u, v) - return closeness_centrality + return closeness_dict diff --git a/networkx/algorithms/centrality/current_flow_betweenness.py b/networkx/algorithms/centrality/current_flow_betweenness.py index 435a1ed7..a18b81ca 100644 --- a/networkx/algorithms/centrality/current_flow_betweenness.py +++ b/networkx/algorithms/centrality/current_flow_betweenness.py @@ -122,14 +122,14 @@ def approximate_current_flow_betweenness_centrality( msg = f"Number random pairs k>kmax ({k}>{kmax}) " raise nx.NetworkXError(msg, "Increase kmax or epsilon") cstar2k = cstar / (2 * k) - for i in range(k): - s, t = seed.sample(range(n), 2) + for _ in range(k): + s, t = pair = seed.sample(range(n), 2) b = np.zeros(n, dtype=dtype) b[s] = 1 b[t] = -1 p = C.solve(b) for v in H: - if v == s or v == t: + if v in pair: continue for nbr in H[v]: w = H[v][nbr].get(weight, 1.0) @@ -318,8 +318,6 @@ def edge_current_flow_betweenness_centrality( .. [2] A measure of betweenness centrality based on random walks, M. E. J. Newman, Social Networks 27, 39-54 (2005). """ - from networkx.utils import reverse_cuthill_mckee_ordering - if not nx.is_connected(G): raise nx.NetworkXError("Graph not connected.") n = G.number_of_nodes() diff --git a/networkx/algorithms/centrality/dispersion.py b/networkx/algorithms/centrality/dispersion.py index 03fcd3ac..8005670c 100644 --- a/networkx/algorithms/centrality/dispersion.py +++ b/networkx/algorithms/centrality/dispersion.py @@ -64,17 +64,13 @@ def dispersion(G, u=None, v=None, normalized=True, alpha=1.0, b=0.0, c=0.0): # neighbors that u and v share embededness = len(ST) + dispersion_val = total if normalized: + dispersion_val = (total + b) ** alpha if embededness + c != 0: - norm_disp = ((total + b) ** alpha) / (embededness + c) - else: - norm_disp = (total + b) ** alpha - dispersion = norm_disp + dispersion_val /= embededness + c - else: - dispersion = total - - return dispersion + return dispersion_val if u is None: # v and u are not specified diff --git a/networkx/algorithms/centrality/eigenvector.py b/networkx/algorithms/centrality/eigenvector.py index 5bcc1b14..f55cedb2 100644 --- a/networkx/algorithms/centrality/eigenvector.py +++ b/networkx/algorithms/centrality/eigenvector.py @@ -117,7 +117,7 @@ def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None, weight=None x = {k: v / nstart_sum for k, v in nstart.items()} nnodes = G.number_of_nodes() # make up to max_iter iterations - for i in range(max_iter): + for _ in range(max_iter): xlast = x x = xlast.copy() # Start with xlast times I to iterate with (A+I) # do the multiplication y^T = x^T A (left eigenvector) @@ -221,7 +221,7 @@ def eigenvector_centrality_numpy(G, weight=None, max_iter=50, tol=0): "cannot compute centrality for the null graph" ) M = nx.to_scipy_sparse_array(G, nodelist=list(G), weight=weight, dtype=float) - eigenvalue, eigenvector = sp.sparse.linalg.eigs( + _, eigenvector = sp.sparse.linalg.eigs( M.T, k=1, which="LR", maxiter=max_iter, tol=tol ) largest = eigenvector.flatten().real diff --git a/networkx/algorithms/centrality/group.py b/networkx/algorithms/centrality/group.py index 7f38d509..5d4e43aa 100644 --- a/networkx/algorithms/centrality/group.py +++ b/networkx/algorithms/centrality/group.py @@ -193,8 +193,7 @@ def group_betweenness_centrality(G, C, normalized=True, weight=None, endpoints=F GBC.append(GBC_group) if list_of_groups: return GBC - else: - return GBC[0] + return GBC[0] def _group_preprocessing(G, set_v, weight): @@ -463,7 +462,7 @@ def _heuristic(k, root, DF_tree, D, nodes, greedy): node_m = DF_tree.number_of_nodes() + 2 added_node = DF_tree.nodes[root]["CL"][0] - # adding the plus nude + # adding the plus node DF_tree.add_nodes_from([(node_p, deepcopy(DF_tree.nodes[root]))]) DF_tree.nodes[node_p]["GM"].append(added_node) DF_tree.nodes[node_p]["GBC"] += DF_tree.nodes[node_p]["cont"][added_node] @@ -508,14 +507,14 @@ def _heuristic(k, root, DF_tree, D, nodes, greedy): DF_tree.nodes[node_p]["betweenness"][x][y] -= ( root_node["betweenness"][added_node][y] * dvxy ) - CL = [ + + DF_tree.nodes[node_p]["CL"] = [ node for _, node in sorted( zip(np.diag(DF_tree.nodes[node_p]["betweenness"]), nodes), reverse=True ) + if node not in DF_tree.nodes[node_p]["GM"] ] - [CL.remove(m) for m in CL if m in DF_tree.nodes[node_p]["GM"]] - DF_tree.nodes[node_p]["CL"] = CL DF_tree.nodes[node_p]["cont"] = dict( zip(nodes, np.diag(DF_tree.nodes[node_p]["betweenness"])) ) diff --git a/networkx/algorithms/centrality/katz.py b/networkx/algorithms/centrality/katz.py index a3acde9b..fd0bb93f 100644 --- a/networkx/algorithms/centrality/katz.py +++ b/networkx/algorithms/centrality/katz.py @@ -165,7 +165,7 @@ def katz_centrality( ) from err # make up to max_iter iterations - for i in range(max_iter): + for _ in range(max_iter): xlast = x x = dict.fromkeys(xlast, 0) # do the multiplication y^T = Alpha * x^T A - Beta diff --git a/networkx/algorithms/centrality/load.py b/networkx/algorithms/centrality/load.py index 358b6560..c27c5fde 100644 --- a/networkx/algorithms/centrality/load.py +++ b/networkx/algorithms/centrality/load.py @@ -65,7 +65,6 @@ def newman_betweenness_centrality(G, v=None, cutoff=None, normalized=True, weigh if order <= 2: return betweenness # no normalization b=0 for all nodes betweenness *= 1.0 / ((order - 1) * (order - 2)) - return betweenness else: betweenness = {}.fromkeys(G, 0.0) for source in betweenness: @@ -79,7 +78,7 @@ def newman_betweenness_centrality(G, v=None, cutoff=None, normalized=True, weigh scale = 1.0 / ((order - 1) * (order - 2)) for v in betweenness: betweenness[v] *= scale - return betweenness # all nodes + return betweenness # all nodes def _node_betweenness(G, source, cutoff=False, normalized=True, weight=None): diff --git a/networkx/algorithms/centrality/percolation.py b/networkx/algorithms/centrality/percolation.py index 52f5569b..4d703380 100644 --- a/networkx/algorithms/centrality/percolation.py +++ b/networkx/algorithms/centrality/percolation.py @@ -99,7 +99,7 @@ def percolation_centrality(G, attribute="percolation", states=None, weight=None) S, P, sigma, _ = dijkstra(G, s, weight) # accumulation percolation = _accumulate_percolation( - percolation, G, S, P, sigma, s, states, p_sigma_x_t + percolation, S, P, sigma, s, states, p_sigma_x_t ) n = len(G) @@ -110,7 +110,7 @@ def percolation_centrality(G, attribute="percolation", states=None, weight=None) return percolation -def _accumulate_percolation(percolation, G, S, P, sigma, s, states, p_sigma_x_t): +def _accumulate_percolation(percolation, S, P, sigma, s, states, p_sigma_x_t): delta = dict.fromkeys(S, 0) while S: w = S.pop() diff --git a/networkx/algorithms/centrality/second_order.py b/networkx/algorithms/centrality/second_order.py index b1cb8b83..3acd69ee 100644 --- a/networkx/algorithms/centrality/second_order.py +++ b/networkx/algorithms/centrality/second_order.py @@ -34,7 +34,6 @@ import networkx as nx from networkx.utils import not_implemented_for # Authors: Erwan Le Merrer (erwan.lemerrer@technicolor.com) -""" Second order centrality measure.""" __all__ = ["second_order_centrality"] diff --git a/networkx/algorithms/centrality/tests/test_dispersion.py b/networkx/algorithms/centrality/tests/test_dispersion.py index fb27efd4..2aac0dec 100644 --- a/networkx/algorithms/centrality/tests/test_dispersion.py +++ b/networkx/algorithms/centrality/tests/test_dispersion.py @@ -56,7 +56,7 @@ class TestDispersion: disp_uv = nx.dispersion(G, "u", "h") assert len(disp) == len(G) assert len(disp_Gu) == len(G) - 1 - assert type(disp_uv) is float + assert isinstance(disp_uv, float) def test_impossible_things(self): G = nx.karate_club_graph() diff --git a/networkx/algorithms/centrality/tests/test_eigenvector_centrality.py b/networkx/algorithms/centrality/tests/test_eigenvector_centrality.py index 0a6e1f89..7a44affa 100644 --- a/networkx/algorithms/centrality/tests/test_eigenvector_centrality.py +++ b/networkx/algorithms/centrality/tests/test_eigenvector_centrality.py @@ -49,7 +49,7 @@ class TestEigenvectorCentrality: def test_maxiter(self): with pytest.raises(nx.PowerIterationFailedConvergence): G = nx.path_graph(3) - b = nx.eigenvector_centrality(G, max_iter=0) + nx.eigenvector_centrality(G, max_iter=0) class TestEigenvectorCentralityDirected: @@ -153,16 +153,16 @@ class TestEigenvectorCentralityDirected: class TestEigenvectorCentralityExceptions: def test_multigraph(self): with pytest.raises(nx.NetworkXException): - e = nx.eigenvector_centrality(nx.MultiGraph()) + nx.eigenvector_centrality(nx.MultiGraph()) def test_multigraph_numpy(self): with pytest.raises(nx.NetworkXException): - e = nx.eigenvector_centrality_numpy(nx.MultiGraph()) + nx.eigenvector_centrality_numpy(nx.MultiGraph()) def test_empty(self): with pytest.raises(nx.NetworkXException): - e = nx.eigenvector_centrality(nx.Graph()) + nx.eigenvector_centrality(nx.Graph()) def test_empty_numpy(self): with pytest.raises(nx.NetworkXException): - e = nx.eigenvector_centrality_numpy(nx.Graph()) + nx.eigenvector_centrality_numpy(nx.Graph()) diff --git a/networkx/algorithms/centrality/tests/test_group.py b/networkx/algorithms/centrality/tests/test_group.py index afa06cdf..3f5559dc 100644 --- a/networkx/algorithms/centrality/tests/test_group.py +++ b/networkx/algorithms/centrality/tests/test_group.py @@ -82,7 +82,7 @@ class TestGroupBetweennessCentrality: Node(s) in C not in graph, raises NodeNotFound exception """ with pytest.raises(nx.NodeNotFound): - b = nx.group_betweenness_centrality(nx.path_graph(5), [4, 7, 8]) + nx.group_betweenness_centrality(nx.path_graph(5), [4, 7, 8]) def test_group_betweenness_directed_weighted(self): """ @@ -152,7 +152,7 @@ class TestProminentGroup: Node(s) in C not in graph, raises NodeNotFound exception """ with pytest.raises(nx.NodeNotFound): - b, g = nx.prominent_group(nx.path_graph(5), 1, C=[10]) + nx.prominent_group(nx.path_graph(5), 1, C=[10]) def test_group_betweenness_directed_weighted(self): """ @@ -217,7 +217,7 @@ class TestGroupClosenessCentrality: Node(s) in S not in graph, raises NodeNotFound exception """ with pytest.raises(nx.NodeNotFound): - c = nx.group_closeness_centrality(nx.path_graph(5), [6, 7, 8]) + nx.group_closeness_centrality(nx.path_graph(5), [6, 7, 8]) class TestGroupDegreeCentrality: @@ -275,4 +275,4 @@ class TestGroupDegreeCentrality: Node(s) in S not in graph, raises NetworkXError """ with pytest.raises(nx.NetworkXError): - b = nx.group_degree_centrality(nx.path_graph(5), [6, 7, 8]) + nx.group_degree_centrality(nx.path_graph(5), [6, 7, 8]) diff --git a/networkx/algorithms/centrality/tests/test_katz_centrality.py b/networkx/algorithms/centrality/tests/test_katz_centrality.py index c7a7fba0..25114533 100644 --- a/networkx/algorithms/centrality/tests/test_katz_centrality.py +++ b/networkx/algorithms/centrality/tests/test_katz_centrality.py @@ -31,7 +31,7 @@ class TestKatzCentrality: def test_maxiter(self): with pytest.raises(nx.PowerIterationFailedConvergence): - b = nx.katz_centrality(nx.path_graph(3), 0.1, max_iter=0) + nx.katz_centrality(nx.path_graph(3), 0.1, max_iter=0) def test_beta_as_scalar(self): alpha = 0.1 @@ -93,7 +93,7 @@ class TestKatzCentrality: def test_multigraph(self): with pytest.raises(nx.NetworkXException): - e = nx.katz_centrality(nx.MultiGraph(), 0.1) + nx.katz_centrality(nx.MultiGraph(), 0.1) def test_empty(self): e = nx.katz_centrality(nx.Graph(), 0.1) @@ -103,12 +103,12 @@ class TestKatzCentrality: with pytest.raises(nx.NetworkXException): G = nx.Graph([(0, 1)]) beta = {0: 77} - e = nx.katz_centrality(G, 0.1, beta=beta) + nx.katz_centrality(G, 0.1, beta=beta) def test_bad_beta_numbe(self): with pytest.raises(nx.NetworkXException): G = nx.Graph([(0, 1)]) - e = nx.katz_centrality(G, 0.1, beta="foo") + nx.katz_centrality(G, 0.1, beta="foo") class TestKatzCentralityNumpy: @@ -127,7 +127,6 @@ class TestKatzCentralityNumpy: b_answer = dict.fromkeys(G, v) for n in sorted(G): assert b[n] == pytest.approx(b_answer[n], abs=1e-7) - nstart = {n: 1 for n in G} b = nx.eigenvector_centrality_numpy(G) for n in sorted(G): assert b[n] == pytest.approx(b_answer[n], abs=1e-3) @@ -201,7 +200,7 @@ class TestKatzCentralityNumpy: def test_multigraph(self): with pytest.raises(nx.NetworkXException): - e = nx.katz_centrality(nx.MultiGraph(), 0.1) + nx.katz_centrality(nx.MultiGraph(), 0.1) def test_empty(self): e = nx.katz_centrality(nx.Graph(), 0.1) @@ -211,12 +210,12 @@ class TestKatzCentralityNumpy: with pytest.raises(nx.NetworkXException): G = nx.Graph([(0, 1)]) beta = {0: 77} - e = nx.katz_centrality_numpy(G, 0.1, beta=beta) + nx.katz_centrality_numpy(G, 0.1, beta=beta) def test_bad_beta_numbe(self): with pytest.raises(nx.NetworkXException): G = nx.Graph([(0, 1)]) - e = nx.katz_centrality_numpy(G, 0.1, beta="foo") + nx.katz_centrality_numpy(G, 0.1, beta="foo") def test_K5_unweighted(self): """Katz centrality: K5""" @@ -227,7 +226,6 @@ class TestKatzCentralityNumpy: b_answer = dict.fromkeys(G, v) for n in sorted(G): assert b[n] == pytest.approx(b_answer[n], abs=1e-7) - nstart = {n: 1 for n in G} b = nx.eigenvector_centrality_numpy(G, weight=None) for n in sorted(G): assert b[n] == pytest.approx(b_answer[n], abs=1e-3) diff --git a/networkx/algorithms/centrality/tests/test_percolation_centrality.py b/networkx/algorithms/centrality/tests/test_percolation_centrality.py index 64790e34..e6758457 100644 --- a/networkx/algorithms/centrality/tests/test_percolation_centrality.py +++ b/networkx/algorithms/centrality/tests/test_percolation_centrality.py @@ -37,16 +37,16 @@ class TestPercolationCentrality: G = example1a_G() p = nx.percolation_centrality(G) p_answer = {4: 0.625, 6: 0.667} - for n in p_answer: - assert p[n] == pytest.approx(p_answer[n], abs=1e-3) + for n, k in p_answer.items(): + assert p[n] == pytest.approx(k, abs=1e-3) def test_percolation_example1b(self): """percolation centrality: example 1a""" G = example1b_G() p = nx.percolation_centrality(G) p_answer = {4: 0.825, 6: 0.4} - for n in p_answer: - assert p[n] == pytest.approx(p_answer[n], abs=1e-3) + for n, k in p_answer.items(): + assert p[n] == pytest.approx(k, abs=1e-3) def test_converge_to_betweenness(self): """percolation centrality: should converge to betweenness diff --git a/networkx/algorithms/centrality/tests/test_subgraph.py b/networkx/algorithms/centrality/tests/test_subgraph.py index a7bbf7b4..71092751 100644 --- a/networkx/algorithms/centrality/tests/test_subgraph.py +++ b/networkx/algorithms/centrality/tests/test_subgraph.py @@ -17,7 +17,7 @@ class TestSubgraph: answer = {0: 1.5430806348152433, 1: 1.5430806348152433} result = subgraph_centrality(nx.path_graph(2)) for k, v in result.items(): - assert answer[k] == pytest.approx(result[k], abs=1e-7) + assert answer[k] == pytest.approx(v, abs=1e-7) answer1 = { "1": 1.6445956054135658, @@ -38,10 +38,10 @@ class TestSubgraph: ) result1 = subgraph_centrality(G1) for k, v in result1.items(): - assert answer1[k] == pytest.approx(result1[k], abs=1e-7) + assert answer1[k] == pytest.approx(v, abs=1e-7) result1 = subgraph_centrality_exp(G1) for k, v in result1.items(): - assert answer1[k] == pytest.approx(result1[k], abs=1e-7) + assert answer1[k] == pytest.approx(v, abs=1e-7) def test_subgraph_centrality_big_graph(self): g199 = nx.complete_graph(199) @@ -66,11 +66,11 @@ class TestSubgraph: answer = {0: 0.1411224421177313, 1: 1.0, 2: 0.1411224421177313} result = communicability_betweenness_centrality(nx.path_graph(3)) for k, v in result.items(): - assert answer[k] == pytest.approx(result[k], abs=1e-7) + assert answer[k] == pytest.approx(v, abs=1e-7) result = communicability_betweenness_centrality(nx.complete_graph(3)) for k, v in result.items(): - assert 0.49786143366223296 == pytest.approx(result[k], abs=1e-7) + assert 0.49786143366223296 == pytest.approx(v, abs=1e-7) def test_communicability_betweenness_centrality(self): answer = { @@ -81,7 +81,7 @@ class TestSubgraph: } result = communicability_betweenness_centrality(nx.path_graph(4)) for k, v in result.items(): - assert answer[k] == pytest.approx(result[k], abs=1e-7) + assert answer[k] == pytest.approx(v, abs=1e-7) answer1 = { "1": 0.060039074193949521, @@ -102,7 +102,7 @@ class TestSubgraph: ) result1 = communicability_betweenness_centrality(G1) for k, v in result1.items(): - assert answer1[k] == pytest.approx(result1[k], abs=1e-7) + assert answer1[k] == pytest.approx(v, abs=1e-7) def test_estrada_index(self): answer = 1041.2470334195475 diff --git a/networkx/algorithms/centrality/voterank_alg.py b/networkx/algorithms/centrality/voterank_alg.py index 27b8fcaf..c28df583 100644 --- a/networkx/algorithms/centrality/voterank_alg.py +++ b/networkx/algorithms/centrality/voterank_alg.py @@ -51,7 +51,7 @@ def voterank(G, number_of_nodes=None): Sci. Rep. 6, 27823; doi: 10.1038/srep27823. """ influential_nodes = [] - voterank = {} + vote_rank = {} if len(G) == 0: return influential_nodes if number_of_nodes is None or number_of_nodes > len(G): @@ -64,29 +64,29 @@ def voterank(G, number_of_nodes=None): 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] + vote_rank[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 + vote_rank[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] + vote_rank[n][0] += vote_rank[nbr][1] if not G.is_directed(): - voterank[nbr][0] += voterank[n][1] + vote_rank[nbr][0] += vote_rank[n][1] for n in influential_nodes: - voterank[n][0] = 0 + vote_rank[n][0] = 0 # step 3 - select top node - n = max(G.nodes, key=lambda x: voterank[x][0]) - if voterank[n][0] == 0: + n = max(G.nodes, key=lambda x: vote_rank[x][0]) + if vote_rank[n][0] == 0: return influential_nodes influential_nodes.append(n) # weaken the selected node - voterank[n] = [0, 0] + vote_rank[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) + vote_rank[nbr][1] -= 1 / avgDegree + vote_rank[nbr][1] = max(vote_rank[nbr][1], 0) return influential_nodes |