Studies On Link Prediction And Information Spreading In Complex Networks

Complex networks describe systems consist of a large number of interacting individuals,while information spreading is a basic form of interaction among individuals.Many real-world spreading phenomena,such as the spreading of opinions,public opinions,news,trends,behaviors,and rumors,can be abstracted as information spreading in complex networks.By employing the method of network analyses,we can characterize the network structures,and then understand the laws of information spreading in networks,eventually achieve intervening and optimizing of the information spreading processes in networks.Revealing the mechanisms and laws of information spreading in complex networks has important real-world applications,for instance,providing a theoretical basis for the warning,prevention,and control of rumors,product marketing,and guiding social trends.Due to the complexity of real-world networks,understanding network structures and information spreading in networks is challenging.On the one hand,due to data protection,technical and man-made reasons,usually,the real-world network structures obtained are noisy.An effective way to identify these noise links is to apply link prediction algorithms to networks.Removing the noises can help to restore the true network structures,and thereby make necessary preparations for analyzing information spreading processes in networks.On the other hand,due to the intricacy of network structures and spreading mechanisms,there are still many difficulties in the theoretical studies of information spreading.For instance,for the problem of optimizing network structure to promote information spreading,the spreading prevalence(i.e.,the objective function for optimization)lacks explicit expression;thus,its optimization usually relies on heuristic methods and lacks analytical results.Another example is,the dynamical equations for coevolving spreading dynamics are usually highly non-linear,and this also brings lots of difficulties to analytical studies.To address the above issues,in this dissertation,we will discuss link prediction and information spreading dynamics in complex networks.The main contents and major contributions of this dissertation are summarized as follows:(1)Link prediction algorithm design and studies of the link predictability problem.Real-world networks have rich structures on all different scales.In order to design more effective link prediction algorithms,it is necessary to incorporate network structure information in multiple scales.This dissertation proposes the loop model and applies it to the problem of link prediction.First,we employ loops of different lengths to characterize the multi-scale structures of networks;then,we apply the exponential random graph model to transfer the loop information to a link prediction algorithm.By extensive experiments on real-world networks,we find that the loop model outperforms other state-of-the-art algorithms in link prediction.The performance of a link prediction algorithm not only decided by itself but also relies on the network under consideration.For instance,for the Erd¨os-R′enyi graph where links are randomly connected,link prediction algorithms cannot perform better than randomly guessing.The dissertation formulates a new question,i.e.,how to characterize the intrinsic link predictability of complex networks;to address the issue,we propose the structural consistency index.The structural consistency index regards the unknown links as a perturbation to the known network,and assume that if the perturbation alters the structure of the known network dramatically,then it is difficult to predict these links;otherwise,it is easy to predict.By applying the matrix perturbation theory,the structural consistency index quantifies the level of dramatic in structure alteration.Extensive experiments reveal that structural consistency is a reasonable estimation of link predictability.Besides,based on the perturbation theory of the adjacency matrix,a new link prediction algorithm,i.e.,the structural perturbation method,can be derived.Experiments show that the proposed algorithm performs well in both prediction accuracy and robustness.Effective link prediction algorithms reduce the noise of networks,thereby providing necessary preparations for further studying dynamics in networks.(2)Optimal interlayer structure design for promoting information spreading in twolayer networks.Real-world networks are rarely independent,and information can spread through different networks in various possible ways.Therefore,many real-world networked systems are necessary to be modeled by multilayer networks,while the interlayer structure of multilayer networks can affect the information spreading dynamics significantly.The dissertation studies the problem of optimal inter-layer structure for maximizing spreading prevalence in two-layer networks.First,we study the optimal inter-layer structure with multiple edges near the spreading threshold.Near the spreading threshold,we derive the expression for the spreading prevalence by applying the eigenvalue perturbation theory.Based on the expression,we prove that the optimal interlayer structure is achieved by greedy connecting nodes with high eigenvector centrality.Numerical experiments reveal that the method proposed in this dissertation outperforms classic heuristic methods.Then,we investigate the optimal interconnecting edge in the general parameter condition.By developing a perturbation theory for discrete-time Markov chains,we give the expression for the spreading prevalence for the two-layer network,thereby derive the optimal inter-layer edge.For small networks,by exhaustively examining all latent edges,we find that the proposed method gives the optimal or near-optimal inter-layer edge.For large networks,the proposed method always outperforms other methods based on static network structures.This dissertation studies the optimization of information spreading from the perspective of network structural perturbation and could provide theoretical support for the optimization of real-world information spreading processes.(3)Studies of critical behaviors of coevolving spreading dynamics.Spreading processes of information,behaviors,and diseases in the real-world are usually not independent.For instance,during the diffusion of ransomware virus WNCRY,information of its solutions and preventions was also spreading quickly,thereby the economic losses had been reduced.These interacting spreading processes are called coevolving spreading.Coevolving spreading can generate complex dynamical behaviors;however,due to the intricacy of coevolving spreading models,systematic theoretical studies are still lacking.Basing on the spectral dimension reduction method,we propose a universal theory for coevolving spreading dynamics in complex networks.Concretely,by coarse-graining the microscopic quenched mean-field equations into two equations in terms of macroscopic observables,we derive the full phase diagram of the coevolving SIS model analytically and give the type of phase transitions between neighboring phase regions.The phase diagram not only verifies critical phenomena that have been known but also predicts those that were previously unknown: such as the interplay between discontinuous transition and hysteresis as well as the emergence of tri-critical points.Besides,we also derive the condition for observing hysteresis.The theory developed in this dissertation could provide an effective method to understand coevolving spreading dynamics;meanwhile,it could also provide a theoretical foundation for the problem of employing one information spreading process to intervene in other information spreading processes.