Spaces:
Running
Running
| """ | |
| Laplacian centrality measures. | |
| """ | |
| import networkx as nx | |
| __all__ = ["laplacian_centrality"] | |
| def laplacian_centrality( | |
| G, normalized=True, nodelist=None, weight="weight", walk_type=None, alpha=0.95 | |
| ): | |
| r"""Compute the Laplacian centrality for nodes in the graph `G`. | |
| The Laplacian Centrality of a node ``i`` is measured by the drop in the | |
| Laplacian Energy after deleting node ``i`` from the graph. The Laplacian Energy | |
| is the sum of the squared eigenvalues of a graph's Laplacian matrix. | |
| .. math:: | |
| C_L(u_i,G) = \frac{(\Delta E)_i}{E_L (G)} = \frac{E_L (G)-E_L (G_i)}{E_L (G)} | |
| E_L (G) = \sum_{i=0}^n \lambda_i^2 | |
| Where $E_L (G)$ is the Laplacian energy of graph `G`, | |
| E_L (G_i) is the Laplacian energy of graph `G` after deleting node ``i`` | |
| and $\lambda_i$ are the eigenvalues of `G`'s Laplacian matrix. | |
| This formula shows the normalized value. Without normalization, | |
| the numerator on the right side is returned. | |
| Parameters | |
| ---------- | |
| G : graph | |
| A networkx graph | |
| normalized : bool (default = True) | |
| If True the centrality score is scaled so the sum over all nodes is 1. | |
| If False the centrality score for each node is the drop in Laplacian | |
| energy when that node is removed. | |
| nodelist : list, optional (default = None) | |
| The rows and columns are ordered according to the nodes in nodelist. | |
| If nodelist is None, then the ordering is produced by G.nodes(). | |
| weight: string or None, optional (default=`weight`) | |
| Optional parameter `weight` to compute the Laplacian matrix. | |
| The edge data key used to compute each value in the matrix. | |
| If None, then each edge has weight 1. | |
| walk_type : string or None, optional (default=None) | |
| Optional parameter `walk_type` used when calling | |
| :func:`directed_laplacian_matrix <networkx.directed_laplacian_matrix>`. | |
| If None, the transition matrix is selected depending on the properties | |
| of the graph. Otherwise can be `random`, `lazy`, or `pagerank`. | |
| alpha : real (default = 0.95) | |
| Optional parameter `alpha` used when calling | |
| :func:`directed_laplacian_matrix <networkx.directed_laplacian_matrix>`. | |
| (1 - alpha) is the teleportation probability used with pagerank. | |
| Returns | |
| ------- | |
| nodes : dictionary | |
| Dictionary of nodes with Laplacian centrality as the value. | |
| Examples | |
| -------- | |
| >>> G = nx.Graph() | |
| >>> edges = [(0, 1, 4), (0, 2, 2), (2, 1, 1), (1, 3, 2), (1, 4, 2), (4, 5, 1)] | |
| >>> G.add_weighted_edges_from(edges) | |
| >>> sorted((v, f"{c:0.2f}") for v, c in laplacian_centrality(G).items()) | |
| [(0, '0.70'), (1, '0.90'), (2, '0.28'), (3, '0.22'), (4, '0.26'), (5, '0.04')] | |
| Notes | |
| ----- | |
| The algorithm is implemented based on [1]_ with an extension to directed graphs | |
| using the ``directed_laplacian_matrix`` function. | |
| Raises | |
| ------ | |
| NetworkXPointlessConcept | |
| If the graph `G` is the null graph. | |
| ZeroDivisionError | |
| If the graph `G` has no edges (is empty) and normalization is requested. | |
| References | |
| ---------- | |
| .. [1] Qi, X., Fuller, E., Wu, Q., Wu, Y., and Zhang, C.-Q. (2012). | |
| Laplacian centrality: A new centrality measure for weighted networks. | |
| Information Sciences, 194:240-253. | |
| https://math.wvu.edu/~cqzhang/Publication-files/my-paper/INS-2012-Laplacian-W.pdf | |
| See Also | |
| -------- | |
| :func:`~networkx.linalg.laplacianmatrix.directed_laplacian_matrix` | |
| :func:`~networkx.linalg.laplacianmatrix.laplacian_matrix` | |
| """ | |
| import numpy as np | |
| import scipy as sp | |
| if len(G) == 0: | |
| raise nx.NetworkXPointlessConcept("null graph has no centrality defined") | |
| if G.size(weight=weight) == 0: | |
| if normalized: | |
| raise ZeroDivisionError("graph with no edges has zero full energy") | |
| return {n: 0 for n in G} | |
| if nodelist is not None: | |
| nodeset = set(G.nbunch_iter(nodelist)) | |
| if len(nodeset) != len(nodelist): | |
| raise nx.NetworkXError("nodelist has duplicate nodes or nodes not in G") | |
| nodes = nodelist + [n for n in G if n not in nodeset] | |
| else: | |
| nodelist = nodes = list(G) | |
| if G.is_directed(): | |
| lap_matrix = nx.directed_laplacian_matrix(G, nodes, weight, walk_type, alpha) | |
| else: | |
| lap_matrix = nx.laplacian_matrix(G, nodes, weight).toarray() | |
| full_energy = np.power(sp.linalg.eigh(lap_matrix, eigvals_only=True), 2).sum() | |
| # calculate laplacian centrality | |
| laplace_centralities_dict = {} | |
| for i, node in enumerate(nodelist): | |
| # remove row and col i from lap_matrix | |
| all_but_i = list(np.arange(lap_matrix.shape[0])) | |
| all_but_i.remove(i) | |
| A_2 = lap_matrix[all_but_i, :][:, all_but_i] | |
| # Adjust diagonal for removed row | |
| new_diag = lap_matrix.diagonal() - abs(lap_matrix[:, i]) | |
| np.fill_diagonal(A_2, new_diag[all_but_i]) | |
| if len(all_but_i) > 0: # catches degenerate case of single node | |
| new_energy = np.power(sp.linalg.eigh(A_2, eigvals_only=True), 2).sum() | |
| else: | |
| new_energy = 0.0 | |
| lapl_cent = full_energy - new_energy | |
| if normalized: | |
| lapl_cent = lapl_cent / full_energy | |
| laplace_centralities_dict[node] = lapl_cent | |
| return laplace_centralities_dict | |