Structural Balance and Random Walks on Complex Networks with Complex
  Weights
Yu Tian Renaud Lambiotte
Complex numbers define the relationship between entities in many situations.
A canonical example would be the off-diagonal terms in a Hamiltonian matrix in
quantum physics. Recent years have seen an increasing interest to extend the
tools of network science when the weight of edges are complex numbers. Here, we
focus on the case when the weight matrix is Hermitian, a reasonable assumption
in many applications, and investigate both structural and dynamical properties
of the complex-weighted networks. Building on concepts from signed graphs, we
introduce a classification of complex-weighted networks based on the notion of
structural balance, and illustrate the shared spectral properties within each
type. We then apply the results to characterise the dynamics of random walks on
complex-weighted networks, where local consensus can be achieved asymptotically
when the graph is structurally balanced, while global consensus will be
obtained when it is strictly unbalanced. Finally, we explore potential
applications of our findings by generalising the notion of cut, and propose an
associated spectral clustering algorithm. We also provide further
characteristics of the magnetic Laplacian, associating directed networks to
complex-weighted ones. The performance of the algorithm is verified on both
synthetic and real networks.