Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUsing higher-order Markov models to reveal flow-based communities in networks
113
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Complex systems made of interacting elements are commonly abstracted as networks, in which nodes are associated with dynamic state variables, whose evolution is driven by interactions mediated by the edges. Markov processes have been the prevailing paradigm to model such a network-based dynamics, for instance in the form of random walks or other types of diffusions. Despite the success of this modelling perspective for numerous applications, it represents an over-simplification of several real-world systems. Importantly, simple Markov models lack memory in their dynamics, an assumption often not realistic in practice. Here, we explore possibilities to enrich the system description by means of second-order Markov models, exploiting empirical pathway information. We focus on the problem of community detection and show that standard network algorithms can be generalized in order to extract novel temporal information about the system under investigation. We also apply our methodology to temporal networks, where we can uncover communities shaped by the temporal correlations in the system. Finally, we discuss relations of the framework of second order Markov processes and the recently proposed formalism of using non-backtracking matrices for community detection.
rate research
Read More
Algorithms for search of communities in networks usually consist discrete variations of links. Here we discuss a flow method, driven by a set of differential equations. Two examples are demonstrated in detail. First is a partition of a signed graph into two parts, where the proposed equations are interpreted in terms of removal of a cognitive dissonance by agents placed in the network nodes. There, the signs and values of links refer to positive or negative interpersonal relationships of different strength. Second is an application of a method akin to the previous one, dedicated to communities identification, to the Sierpinski triangle of finite size. During the time evolution, the related graphs are weighted; yet at the end the discrete character of links is restored. In the case of the Sierpinski triangle, the method is supplemented by adding a small noise to the initial connectivity matrix. By breaking the symmetry of the network, this allows to a successful handling of overlapping nodes.
Complex networks represent the natural backbone to study epidemic processes in populations of interacting individuals. Such a modeling framework, however, is naturally limited to pairwise interactions, making it less suitable to properly describe social contagion, where individuals acquire new norms or ideas after simultaneous exposure to multiple sources of infections. Simplicial contagion has been proposed as an alternative framework where simplices are used to encode group interactions of any order. The presence of higher-order interactions leads to explosive epidemic transitions and bistability which cannot be obtained when only dyadic ties are considered. In particular, critical mass effects can emerge even for infectivity values below the standard pairwise epidemic threshold, where the size of the initial seed of infectious nodes determines whether the system would eventually fall in the endemic or the healthy state. Here we extend simplicial contagion to time-varying networks, where pairwise and higher-order simplices can be created or destroyed over time. By following a microscopic Markov chain approach, we find that the same seed of infectious nodes might or might not lead to an endemic stationary state, depending on the temporal properties of the underlying network structure, and show that persistent temporal interactions anticipate the onset of the endemic state in finite-size systems. We characterize this behavior on higher-order networks with a prescribed temporal correlation between consecutive interactions and on heterogeneous simplicial complexes, showing that temporality again limits the effect of higher-order spreading, but in a less pronounced way than for homogeneous structures. Our work suggests the importance of incorporating temporality, a realistic feature of many real-world systems, into the investigation of dynamical processes beyond pairwise interactions.
Researchers use community-detection algorithms to reveal large-scale organization in biological and social networks, but community detection is useful only if the communities are significant and not a result of noisy data. To assess the statistical significance of the network communities, or the robustness of the detected structure, one approach is to perturb the network structure by removing links and measure how much the communities change. However, perturbing sparse networks is challenging because they are inherently sensitive; they shatter easily if links are removed. Here we propose a simple method to perturb sparse networks and assess the significance of their communities. We generate resampled networks by adding extra links based on local information, then we aggregate the information from multiple resampled networks to find a coarse-grained description of significant clusters. In addition to testing our method on benchmark networks, we use our method on the sparse network of the European Court of Justice (ECJ) case law, to detect significant and insignificant areas of law. We use our significance analysis to draw a map of the ECJ case law network that reveals the relations between the areas of law.
We use the information present in a bipartite network to detect cores of communities of each set of the bipartite system. Cores of communities are found by investigating statistically validated projected networks obtained using information present in the bipartite network. Cores of communities are highly informative and robust with respect to the presence of errors or missing entries in the bipartite network. We assess the statistical robustness of cores by investigating an artificial benchmark network, the co-authorship network, and the actor-movie network. The accuracy and precision of the partition obtained with respect to the reference partition are measured in terms of the adjusted Rand index and of the adjusted Wallace index respectively. The detection of cores is highly precise although the accuracy of the methodology can be limited in some cases.
For Agent Based Models, in particular the Voter Model (VM), a general framework of aggregation is developed which exploits the symmetries of the agent network $G$. Depending on the symmetry group $Aut_{omega} (N)$ of the weighted agent network, certain ensembles of agent configurations can be interchanged without affecting the dynamical properties of the VM. These configurations can be aggregated into the same macro state and the dynamical process projected onto these states is, contrary to the general case, still a Markov chain. The method facilitates the analysis of the relation between microscopic processes and a their aggregation to a macroscopic level of description and informs about the complexity of a system introduced by heterogeneous interaction relations. In some cases the macro chain is solvable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
