diff options
| author | Martha Frysztacki [frɨʂtat͡skʲ] <martha.frysztacki@kit.edu> | 2021-03-24 19:46:48 +0100 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-03-24 11:46:48 -0700 |
| commit | 5cee6a56a63cb25bc1e109727792ad6a91be93b3 (patch) | |
| tree | a6f3d0374c0f7b1ed48d1448081b223fb71b1b28 | |
| parent | 4a5bcf56399229b96a432497377b69cf4456b0ff (diff) | |
| download | networkx-5cee6a56a63cb25bc1e109727792ad6a91be93b3.tar.gz | |
modularity_max: account for edge weights (#4690)
Include edge weights in modularity_max computation.
Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
| -rw-r--r-- | networkx/algorithms/community/modularity_max.py | 16 | ||||
| -rw-r--r-- | networkx/algorithms/community/tests/test_modularity_max.py | 13 |
2 files changed, 21 insertions, 8 deletions
diff --git a/networkx/algorithms/community/modularity_max.py b/networkx/algorithms/community/modularity_max.py index cac64eb5..eb2a7f49 100644 --- a/networkx/algorithms/community/modularity_max.py +++ b/networkx/algorithms/community/modularity_max.py @@ -1,8 +1,4 @@ -# TODO: -# - Alter equations for weighted case -# - Write tests for weighted case -"""Functions for detecting communities based on modularity. -""" +"""Functions for detecting communities based on modularity.""" from networkx.algorithms.community.quality import modularity @@ -19,8 +15,7 @@ def greedy_modularity_communities(G, weight=None, resolution=1): """Find communities in G using greedy modularity maximization. This function uses Clauset-Newman-Moore greedy modularity maximization [2]_. - This method currently supports the Graph class and does not - consider edge weights. + This method currently supports the Graph class. Greedy modularity maximization begins with each node in its own community and joins the pair of communities that most increases modularity until no @@ -33,6 +28,10 @@ def greedy_modularity_communities(G, weight=None, resolution=1): Parameters ---------- G : NetworkX graph + weight : string or None, optional (default=None) + The name of an edge attribute that holds the numerical value used + as a weight. If None, then each edge has weight 1. + The degree is the sum of the edge weights adjacent to the node. Returns ------- @@ -93,7 +92,8 @@ def greedy_modularity_communities(G, weight=None, resolution=1): a = [k[i] * q0 for i in range(N)] dq_dict = { i: { - j: 2 * q0 - 2 * resolution * k[i] * k[j] * q0 * q0 + j: 2 * q0 * G.get_edge_data(i, j).get(weight, 1.0) + - 2 * resolution * k[i] * k[j] * q0 * q0 for j in [node_for_label[u] for u in G.neighbors(label_for_node[i])] if j != i } diff --git a/networkx/algorithms/community/tests/test_modularity_max.py b/networkx/algorithms/community/tests/test_modularity_max.py index c6fe3fa2..23103d4b 100644 --- a/networkx/algorithms/community/tests/test_modularity_max.py +++ b/networkx/algorithms/community/tests/test_modularity_max.py @@ -24,6 +24,19 @@ def test_modularity_communities(func): assert set(func(G)) == expected +def test_modularity_communities_weighted(): + G = nx.balanced_tree(2, 3) + for (a, b) in G.edges: + if ((a == 1) or (a == 2)) and (b != 0): + G[a][b]["weight"] = 10.0 + else: + G[a][b]["weight"] = 1.0 + + expected = [{0, 1, 3, 4, 7, 8, 9, 10}, {2, 5, 6, 11, 12, 13, 14}] + + assert greedy_modularity_communities(G, weight="weight") == expected + + def test_resolution_parameter_impact(): G = nx.barbell_graph(5, 3) |