An improved belief propagation algorithm for detecting mesoscale structure in complex networks.

The framework of statistical inference has been successfully used to detect the mesoscale structures in complex networks such as community structure and core-periphery (CP) structure. The main principle is that the stochastic block model is used to fit the observed network and the learned parameters indicating the group assignment, in which the parameters of model are often calculated via an expectation-maximization algorithm and a belief propagation (BP) algorithm, is implemented to calculate the decomposition itself. In the derivation process of the BP algorithm, some approximations were made by omitting the effects of node's neighbors, the approximations do not hold if the degrees of some nodes are extremely large. As a result, for example, the BP algorithm cannot detect the CP structure in networks and even yields a wrong detection because the nodal degrees in the core group are very large. In doing so, we propose an improved BP algorithm to solve the problem in the original BP algorithm without increasing any computational complexity. We find that the original and the improved BP algorithms yield a similar performance regarding the community detection; however, our improved BP algorithm is much better and more stable when the CP structure becomes more dominant. The improved BP algorithm may help us correctly partition different types of mesoscale structures in networks.

Reconstructing signed networks via Ising dynamics.

Revealing unknown network structure from observed data is a fundamental inverse problem in network science. Current reconstruction approaches were mainly proposed to infer the unsigned networks. However, many social relationships, such as friends and foes, can be represented as signed social networks that contain positive and negative links. To the best of our knowledge, the method of reconstructing signed networks has not yet been developed. To this purpose, we develop a statistical inference approach to fully reconstruct the signed network structure (positive links, negative links, and nonexistent links) based on the Ising dynamics. By the theoretical analysis, we show that our approach can transfer the problem of maximum likelihood estimation into the problem of solving linear systems of equations, where the solution of the linear system of equations uncovers the neighbors and the signs of links of each node. The experimental results on both synthetic and empirical networks validate the reliability and efficiency of our method. Our study moves the first step toward reconstructing signed networks.

Detection of core-periphery structure in networks based on 3-tuple motifs.

Detecting mesoscale structure, such as community structure, is of vital importance for analyzing complex networks. Recently, a new mesoscale structure, core-periphery (CP) structure, has been identified in many real-world systems. In this paper, we propose an effective algorithm for detecting CP structure based on a 3-tuple motif. In this algorithm, we first define a 3-tuple motif in terms of the patterns of edges as well as the property of nodes, and then a motif adjacency matrix is constructed based on the 3-tuple motif. Finally, the problem is converted to find a cluster that minimizes the smallest motif conductance. Our algorithm works well in different CP structures: including single or multiple CP structure, and local or global CP structures. Results on the synthetic and the empirical networks validate the high performance of our method.

A unified method of detecting core-periphery structure and community structure in networks.

The core-periphery structure and the community structure are two typical meso-scale structures in complex networks. Although community detection has been extensively investigated from different perspectives, the definition and the detection of the core-periphery structure have not received much attention. Furthermore, the detection problems of the core-periphery and community structure were separately investigated. In this paper, we develop a unified framework to simultaneously detect the core-periphery structure and community structure in complex networks. Moreover, there are several extra advantages of our algorithm: our method can detect not only single but also multiple pairs of core-periphery structures; the overlapping nodes belonging to different communities can be identified; different scales of core-periphery structures can be detected by adjusting the size of the core. The good performance of the method has been validated on synthetic and real complex networks. So, we provide a basic framework to detect the two typical meso-scale structures: the core-periphery structure and the community structure.

Interplay between the local information based behavioral responses and the epidemic spreading in complex networks.

The spreading of an infectious disease can trigger human behavior responses to the disease, which in turn plays a crucial role on the spreading of epidemic. In this study, to illustrate the impacts of the human behavioral responses, a new class of individuals, S(F), is introduced to the classical susceptible-infected-recovered model. In the model, S(F) state represents that susceptible individuals who take self-initiate protective measures to lower the probability of being infected, and a susceptible individual may go to S(F) state with a response rate when contacting an infectious neighbor. Via the percolation method, the theoretical formulas for the epidemic threshold as well as the prevalence of epidemic are derived. Our finding indicates that, with the increasing of the response rate, the epidemic threshold is enhanced and the prevalence of epidemic is reduced. The analytical results are also verified by the numerical simulations. In addition, we demonstrate that, because the mean field method neglects the dynamic correlations, a wrong result based on the mean field method is obtained-the epidemic threshold is not related to the response rate, i.e., the additional S(F) state has no impact on the epidemic threshold.

Full reconstruction of simplicial complexes from binary contagion and Ising data.

Previous efforts on data-based reconstruction focused on complex networks with pairwise or two-body interactions. There is a growing interest in networks with higher-order or many-body interactions, raising the need to reconstruct such networks based on observational data. We develop a general framework combining statistical inference and expectation maximization to fully reconstruct 2-simplicial complexes with two- and three-body interactions based on binary time-series data from two types of discrete-state dynamics. We further articulate a two-step scheme to improve the reconstruction accuracy while significantly reducing the computational load. Through synthetic and real-world 2-simplicial complexes, we validate the framework by showing that all the connections can be faithfully identified and the full topology of the 2-simplicial complexes can be inferred. The effects of noisy data or stochastic disturbance are studied, demonstrating the robustness of the proposed framework.

Statistical inference approach to structural reconstruction of complex networks from binary time series.

Complex networks hosting binary-state dynamics arise in a variety of contexts. In spite of previous works, to fully reconstruct the network structure from observed binary data remains challenging. We articulate a statistical inference based approach to this problem. In particular, exploiting the expectation-maximization (EM) algorithm, we develop a method to ascertain the neighbors of any node in the network based solely on binary data, thereby recovering the full topology of the network. A key ingredient of our method is the maximum-likelihood estimation of the probabilities associated with actual or nonexistent links, and we show that the EM algorithm can distinguish the two kinds of probability values without any ambiguity, insofar as the length of the available binary time series is reasonably long. Our method does not require any a priori knowledge of the detailed dynamical processes, is parameter-free, and is capable of accurate reconstruction even in the presence of noise. We demonstrate the method using combinations of distinct types of binary dynamical processes and network topologies, and provide a physical understanding of the underlying reconstruction mechanism. Our statistical inference based reconstruction method contributes an additional piece to the rapidly expanding "toolbox" of data based reverse engineering of complex networked systems.

Solitons as candidates for energy carriers in Fermi-Pasta-Ulam lattices.

Currently, effective phonons (renormalized or interacting phonons) rather than solitary waves (for short, solitons) are regarded as the energy carriers in nonlinear lattices. In this work, by using the approximate soliton solutions of the corresponding equations of motion and adopting the Boltzmann distribution for these solitons, the average velocities of solitons are obtained and are compared with the sound velocities of energy transfer. Excellent agreements with the numerical results and the predictions of other existing theories are shown in both the symmetric Fermi-Pasta-Ulam-ß lattices and the asymmetric Fermi-Pasta-Ulam-αß lattices. These clearly indicate that solitons are suitable candidates for energy carriers in Fermi-Pasta-Ulam lattices. In addition, the root-mean-square velocity of solitons can be obtained from the effective phonons theory.