r""" Returns the modularity of the given partition of the graph. Modularity is defined in [1]_ as .. math:: Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_ik_j}{2m}\right) \delta(c_i,c_j) where m is the number of edges, A is the adjacency matrix of `G`,
(G, communities, weight="weight")
| 8 | |
| 9 | @not_implemented_for("multigraph") |
| 10 | def modularity(G, communities, weight="weight"): |
| 11 | r""" |
| 12 | Returns the modularity of the given partition of the graph. |
| 13 | Modularity is defined in [1]_ as |
| 14 | |
| 15 | .. math:: |
| 16 | |
| 17 | Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_ik_j}{2m}\right) |
| 18 | \delta(c_i,c_j) |
| 19 | |
| 20 | where m is the number of edges, A is the adjacency matrix of |
| 21 | `G`, |
| 22 | |
| 23 | .. math:: |
| 24 | |
| 25 | k_i\ is\ the\ degree\ of\ i\ and\ \delta(c_i, c_j)\ is\ 1\ if\ i\ and\ j\ are\ in\ the\ same\ community\ and\ 0\ otherwise. |
| 26 | |
| 27 | Parameters |
| 28 | ---------- |
| 29 | G : easygraph.Graph or easygraph.DiGraph |
| 30 | |
| 31 | communities : list or iterable of set of nodes |
| 32 | These node sets must represent a partition of G's nodes. |
| 33 | |
| 34 | weight : string, optional (default : 'weight') |
| 35 | The key for edge weight. |
| 36 | |
| 37 | Returns |
| 38 | ---------- |
| 39 | Q : float |
| 40 | The modularity of the partition. |
| 41 | |
| 42 | References |
| 43 | ---------- |
| 44 | .. [1] M. E. J. Newman *Networks: An Introduction*, page 224. |
| 45 | Oxford University Press, 2011. |
| 46 | |
| 47 | """ |
| 48 | # TODO: multigraph not included. |
| 49 | |
| 50 | if not isinstance(communities, list): |
| 51 | communities = list(communities) |
| 52 | |
| 53 | directed = G.is_directed() |
| 54 | m = G.size(weight=weight) |
| 55 | if directed: |
| 56 | out_degree = dict(G.out_degree(weight=weight)) |
| 57 | in_degree = dict(G.in_degree(weight=weight)) |
| 58 | norm = 1 / m |
| 59 | else: |
| 60 | out_degree = dict(G.degree(weight=weight)) |
| 61 | in_degree = out_degree |
| 62 | norm = 1 / (2 * m) |
| 63 | |
| 64 | def val(u, v): |
| 65 | try: |
| 66 | w = G[u][v].get(weight, 1) |
| 67 | except KeyError: |
no test coverage detected