Complex networks with complex weights

In many studies, it is common to use binary (i.e., unweighted) edges to examine networks of entities that are either adjacent or not adjacent. Researchers have generalized such binary networks to incorporate edge weights, which allow one to encode node–node interactions with heterogeneous intensities or frequencies (e.g., in transportation networks, supply chains, and social networks). Most such studies have considered real-valued weights, despite the fact that networks with complex weights arise in fields as diverse as quantum information, quantum chemistry, electrodynamics, rheology, and machine learning. Many of the standard network-science approaches in the study of classical systems rely on the real-valued nature of edge weights, so it is necessary to generalize them if one seeks to use them to analyze networks with complex edge weights. In this paper, we examine how standard network-analysis methods fail to capture structural features of networks with complex edge weights. We then generalize several network measures to the complex domain and show that random-walk centralities provide a useful approach to examine node importances in networks with complex weights.

Figure 1

Examples of networks with real and complex edge weights. Each of these networks is a closed and directed triad. (a) The weight matrix $W$ is stochastic. It induces random-walk dynamics $\dot{\mathbf{x}}\left(t\right)=-H_{\mathrm{c}}\mathbf{x}\left(t\right)$, where $H_{\mathrm{c}}=\mathbb{1}-W$ and $\mathbf{x}\left(t\right)$ is a probability vector whose entries $x_i\left(t\right)$ (with $i\in \{1,2,3\}$) give the probabilities of finding a random walker at each node $i$ at time $t$. (b) The weight matrix $W$ is Hermitian. It induces a continuous-time quantum walk $\dot{|\psi \rangle }=-\mathrm{i}{H}_{\mathrm{q}}|\psi \rangle$, where $|\psi \rangle \in {\mathbb{C}}^3$ and $H_{\mathrm{q}}=-W$.

Figure 2

Classical and quantum consensus. The evolution of the (a) classical consensus (12) and (b) quantum consensus (14). The underlying network is one network from a $G(N,p)$ Erdős–Rényi (ER) random-graph model with $N=100$ nodes and connection probability $p=0.2$. The solid black curves indicate the amount of consensus in the unweighted models, and the dashed orange curves indicate the amount of consensus in the weighted models. For the weighted DeGroot model (3), we set $w_{ij}=a_{ij}/k_i$. Additionally, we set $w_{ij}=e^{-\mathrm{i}\pi /4}$ and $w_{ij}^{\prime }=e^{\mathrm{i}\pi /4}$ for all $i$ and $j$ in the weighted Hamiltonian (10). In panel (a), we compute $\mathbf{x}\left(t\right)$ in $r_{\mathrm{c}}\left(t\right)$ by evaluating $e^{(W-\mathbb{1})t}\mathbf{x}\left(0\right)$, where $x_1\left(0\right)=1$ and $x_j\left(0\right)=0$ for $j\in \{2,\cdots ,N\}$. In panel (b), we use an implicit unitary integrator to solve Eq. (4) with the Hamiltonian (10). We normalize each initial wave-function component $|{\psi }_i\left(0\right)\rangle$ (with $i\in \{1,\cdots ,N\}$) to 1, and we uniformly randomly distribute their phases with mean $\pi /3$ and variance $25/3$.

Figure 3

Examples of clustering coefficients in a network with complex edge weights. (a) A closed and directed triad with complex weights $e^{\mathrm{i}\phi }$. The weighted clustering coefficient of node $i$ (in green) is $c_i^{\mathrm{w}}=e^{\mathrm{i}\phi }$. (b) A closed and directed triad with complex weights $e^{\pm \mathrm{i}\phi }$. The weighted clustering coefficient of node $i$ (in green) is $c_i^{\mathrm{w}}=cos\left(\phi \right)$.

Figure 4

Graph energies for different networks with binary, real, and complex edge weights. We show the graph energies $E\left(G\right)$ [see Eq. (24)] for five types of networks with binary, real, and complex weight distributions: (a) a $G(N,p)$ ER network, (b) a stochastic block model (SBM) with two $G(N,p)$ ER blocks and interblock connection probability ${10}^{-3}$, (c) an SBM with one $G(N,p)$ ER block for general $p$, one $G(N,p)$ ER block with $p={10}^{-3}$, and interblock connection probability ${10}^{-3}$, (d) a $G(N,k,q)$ Watts–Strogatz (WS) network in which each node is adjacent to $k=4$ nearest neighbors (where $q$ denotes the probability of rewiring each edge), and (e) a Barabási–Albert (BA) network. All of these networks have $N=1000$ nodes. In all simulations that involve weighted networks, we use Hermitian weight matrices (i.e., $W=W^{†}$). To construct the BA network, we start with a star graph with 1 hub and $m$ leaves, and we iteratively add new nodes until there are 1000 nodes. Each new node has $m$ edges that connect to existing nodes using linear preferential attachment. The orange disks indicate numerical results for binary weight matrices (i.e., for $W=A$). The green triangles indicate numerical results for networks with real-valued weight distributions, and the blue diamonds indicate numerical results for networks with complex-valued weight distributions. The real weights are distributed uniformly in the interval $[0,4/3)$, and the complex weights are distributed uniformly in the subset of the open unit disk in the first quadrant of the complex plane. All reported results are means of 100 independent instantiations of the indicated random-graph models. For each instantiation, we use the same network structure, but we change the weights (which can be binary, real, or complex). The dashed gray curves in panels (a)–(c) are based on the analytical solutions (25), (B4), and (B5), which assume that $N\to \infty$.

Figure 5

Betweenness and closeness centralities of a network with three nodes and the weight matrix (30). In the table, we show the geodesic betweenness and closeness centralities of nodes 1, 2, and 3 that are associated with the unweighted (i.e., binary) analog of the depicted network.

Figure 6

Quantum random-walk versus geodesic betweenness and closeness centralities. We illustrate the correlations between quantum random-walk (qw) and geodesic centralities for (a, b) betweenness and (c, d) closeness. In panels (a) and (c), we show scatter plots for a $G(N,p)$ ER network with $p=0.1$. In panels (b) and (d), we show scatter plots for a BA network that we construct from an initial star graph with 1 hub and 2 leaves by iteratively adding new nodes until there are $N=1000$ nodes. Each new node has $m=2$ edges that connect to existing nodes using linear preferential attachment. Both networks have 1000 nodes. The Pearson correlation coefficients are (a) 0.89, (b) 0.81, (c) 1.00, and (d) 0.36. We calculate the geodesic centralities for binary networks. To calculate the quantum random-walk centralities, we use $H_{\mathrm{q}}=-W$ [see Eq. (4)] as the evolution operator. We suppose that $W$ is Hermitian, so $W=W^{†}$. Aside from the Hermiticity constraint, we distribute the weights uniformly at random in the subset of the open unit disk in the first quadrant of the complex plane.

Figure 7

Eigenvalue distributions for different networks with binary, real, and complex edge weights. We show the eigenvalue distributions for five types of networks with binary, real, and complex weight distributions: (a) a $G(N,p)$ ER network with $p=1/9$ (where $p$ is the connection probability), (b) an SBM with two $G(N,p)$ ER blocks with $p=1/9$ and interblock connection probability ${10}^{-3}$, (c) an SBM with one $G(N,p)$ ER block with $p=1/9$, one $G(N,p)$ ER block with $p={10}^{-3}$, and interblock connection probability ${10}^{-3}$, (d) a $G(N,k,q)$ WS network in which $q=1/9$ and each node is adjacent to $k=4$ nearest neighbors (where $q$ is the probability of rewiring each edge), and (e) a BA network. All of these networks have $N=1000$ nodes. In all simulations with weighted networks, we use Hermitian weight matrices (i.e., $W=W^{†}$). To construct the BA network, we start with a star graph with 1 hub and 2 leaves and iteratively add new nodes until there are $N=1000$ nodes. Each new node has $m=2$ edges that connect to existing nodes using linear preferential attachment. The solid orange curves indicate numerical results for binary weight matrices (i.e., for $W=A$). The dotted green curves indicate numerical results for real-valued weight distributions, and the dashed blue curves indicate numerical results for networks with complex-valued weight distributions. We distribute the real weights uniformly at random in the interval $[0,4/3)$, and we distribute the complex weights uniformly at random in the subset of the open unit disk in the first quadrant of the complex plane. Each result is a mean of 100 independent instantiations of the indicated random-graph models. For each instantiation, we use the same network structure, but we change the weights (which can be binary, real, or complex). The solid gray curves in panel (a) indicate the analytical solution (B1) for ${\sigma }_2^2=p(1-p), {\sigma }_2^2=4(4-3p)p/27$, and ${\sigma }_2^2=p/2-32p^2/\left(9{\pi }^2\right)$ [see Eqs. (B3, B4, B5)].