Source code for netrd.distance.dmeasure


Distance measure based on the Jensen-Shannon Divergence
between the network node dispersion distributions of two graphs.

Schieber, T. A. et al.
Quantification of network structural dissimilarities.
Nat. Commun. 8, 13928 (2017).

author: Brennan Klein
Submitted as part of the 2019 NetSI Collabathon.


from collections import Counter
import networkx as nx
import numpy as np
from scipy.stats import entropy
from .base import BaseDistance
from ..utilities.entropy import js_divergence
from ..utilities import undirected

[docs]class DMeasure(BaseDistance): """Compare two graphs by their network node dispersion."""
[docs] @undirected def dist(self, G1, G2, w1=0.45, w2=0.45, w3=0.10, niter=50): r"""The D-Measure is a comparison of structural dissimilarities between graphs. The key concept is the network node dispersion .. math:: NND(G) = \frac{\mathcal{J}(\mathbf{P}_1,\ldots,\mathbf{P}_N)}{\log(d+1)}, where :math:`\mathcal{J}` is the Jenson-Shannon divergence between :math:`N` node-distance distributions .. math:: \mathbf{P}_i = \{p_i(j)\}, and :math:`p_i(j)` is the fraction of nodes at distance :math:`i` from node :math:`j`. The D-measure itself is a weighted sum of three components: the square root of the Jensen-Shannon divergence between the average node-distance probabilities of the two graphs .. math:: \mu_j = \frac{1}{N}\sum_{i=1}^N p_i(j), the second term is the absolute value of the differences in the square roots of the network node dispersions of the two graphs, and the third term is the sum of the square roots of the Jensen-Shannon divergences between the probability distributions of the alpha centralities of two graph and of their complements. Parameters ---------- G1 (nx.Graph): the first graph to be compared. G2 (nx.Graph): the second graph to be compared. w1 (float): weight of the first term in the calculation; with w2 and w3, must sum to 1.0. w2 (float): weight of the second term in the calculation; with w1 and w3, must sum to 1.0. w3 (float): weight of the third term in the calculation; with w1 d w2, must sum to 1.0. niter (int): the alpha centralities are calculated using power iteration, with this many iterations Returns ------- dist (float): between 0 and 1, the D-measure distance between G1 and G2 Notes ----- The default values for w1, w2, and w3 are from the original paper. References ---------- .. [1] Schieber, T. A. et al. Quantification of network structural dissimilarities. Nat. Commun. 8, 13928 (2017). """ if sum([w1, w2, w3]) != 1: raise ValueError("Weights must sum to one.") first_term = 0 second_term = 0 third_term = 0 if w1 + w2 > 0: g1_nnd, g1_pdfs = network_node_dispersion(G1) g2_nnd, g2_pdfs = network_node_dispersion(G2) first_term = np.sqrt(js_divergence(g1_pdfs, g2_pdfs)) second_term = np.abs(np.sqrt(g1_nnd) - np.sqrt(g2_nnd)) if w3 > 0: def alpha_jsd(G1, G2): """ Compute the Jensen-Shannon divergence between the alpha-centrality probability distributions of two graphs. """ p1 = alpha_centrality_prob(G1, niter=niter) p2 = alpha_centrality_prob(G2, niter=niter) m = max([len(p1), len(p2)]) P1 = np.zeros(m) P2 = np.zeros(m) P1[(m - len(p1)) : m] = p1 P2[(m - len(p2)) : m] = p2 return js_divergence(P1, P2) G1c = nx.complement(G1) G2c = nx.complement(G2) first_jsd = alpha_jsd(G1, G2) second_jsd = alpha_jsd(G1c, G2c) third_term = 0.5 * (np.sqrt(first_jsd) + np.sqrt(second_jsd)) dist = w1 * first_term + w2 * second_term + w3 * third_term self.results["components"] = (first_term, second_term, third_term) self.results["weights"] = (w1, w2, w3) self.results["dist"] = dist return dist
def shortest_path_matrix(G): """ Return a matrix of pairwise shortest path lengths between nodes. Parameters ---------- G (nx.Graph): the graph in question Returns ------- pmat (np.ndarray): a matrix of shortest paths between nodes in G """ N = G.number_of_nodes() pmat = np.zeros((N, N)) + N paths = nx.all_pairs_shortest_path_length(G) for node_i, node_ij in paths: for node_j, length_ij in node_ij.items(): pmat[node_i, node_j] = length_ij pmat[pmat == np.inf] = N return pmat def node_distance(G): """ Return an NxN matrix that consists of histograms of shortest path lengths between nodes i and j. This is useful for eventually taking information theoretic distances between the nodes. Parameters ---------- G (nx.Graph): the graph in question. Returns ------- out (np.ndarray): a matrix of binned node distance values. """ N = G.number_of_nodes() a = np.zeros((N, N)) dists = nx.shortest_path_length(G) for idx, row in enumerate(dists): counts = Counter(row[1].values()) a[idx] = [counts[l] for l in range(1, N + 1)] return a / (N - 1) def network_node_dispersion(G): """ This function calculates the network node dispersion of a graph G. This function also returns the average of the each node-distance distribution. Parameters ---------- G (nx.Graph): the graph in question. Returns ------- nnd (float): the nearest node dispersion nd_vec (np.ndarray): a vector of averages of the node-distance distributions """ N = G.number_of_nodes() nd = node_distance(G) pdfm = np.mean(nd, axis=0) # NOTE: the paper says that the normalization is the diameter plus one, # but the previous implementation uses the number of nonzero entries in the # node-distance matrix. This number should typically be the diameter plus # one anyway. norm = np.log(nx.diameter(G) + 1) ndf = nd.flatten() # calculate the entropy, with the convention that 0/0 = 0 entr = -1 * sum(ndf * np.log(ndf, out=np.zeros_like(ndf), where=(ndf != 0))) nnd = max([0, entropy(pdfm) - entr / N]) / norm return nnd, pdfm def alpha_centrality_prob(G, niter): """ Returns a probability distribution over alpha centralities for the network. Parameters ---------- G (nx.Graph): the graph in question. niter (int): the number of iterations needed to converge properly. Returns: alpha_prob (np.ndarray): a vector of probabilities for each node in G. """ # calculate the alpha centrality for each node N = G.number_of_nodes() alpha = 1 / N A = nx.to_numpy_array(G) s = A.sum(axis=1) cr = s.copy() for _ in range(niter): cr = s + alpha * # turn the alpha centralities into a probability distribution cr = cr / (N - 1) r = sorted(cr / (N**2)) alpha_prob = list(r) + [max([0, 1 - sum(r)])] return np.array(alpha_prob)