Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSpectral density of equitable core-periphery graphs
81
0
0.0
(
0
)
Authors
Paolo Barucca
Ask ChatGPT about the research
No Arabic abstract
Core-periphery structure is an emerging property of a wide range of complex systems and indicate the presence of group of actors in the system with an higher number of connections among them and a lower number of connections with a sparsely connected periphery. The dynamics of a complex system which is interacting on a given graph structure is strictly connected with the spectral properties of the graph itself, nevertheless it is generally extremely hard to obtain analytic results which will hold for arbitrary large systems. Recently a statistical ensemble of random graphs with a regular block structure, i.e. the ensemble of equitable graphs, has been introduced and analytic results have been derived in the computationally-hard context of graph partitioning and community detection. In this paper, we present a general analytic result for a ensemble of equitable core-periphery graphs, yielding a new explicit formula for the spectral density of networks with core-periphery structure.
rate research
Read More
Graph partitioning problems emerge in a wide variety of complex systems, ranging from biology to finance, but can be rigorously analyzed and solved only for a few graph ensembles. Here, an ensemble of equitable graphs, i.e. random graphs with a block-regular structure, is studied, for which analytical results can be obtained. In particular, the spectral density of this ensemble is computed exactly for a modular and bipartite structure. Kesten-McKays law for random regular graphs is found analytically to apply also for modular and bipartite structures when blocks are homogeneous. Exact solution to graph partitioning for two equal-sized communities is proposed and verified numerically, and a conjecture on the absence of an efficient recovery detectability transition in equitable graphs is suggested. Final discussion summarizes results and outlines their relevance for the solution of graph partitioning problems in other graph ensembles, in particular for the study of detectability thresholds and resolution limits in stochastic block models.
Core-periphery networks are structures that present a set of central and densely connected nodes, namely the core, and a set of non-central and sparsely connected nodes, namely the periphery. The rich-club refers to a set in which the highest degree nodes show a high density of connections. Thus, a network that displays a rich-club can be interpreted as a core-periphery network in which the core is made up by a number of hubs. In this paper, we test the resilience of networks showing a progressively denser rich-club and we observe how this structure is able to affect the network measures in terms of both cohesion and efficiency in information flow. Additionally, we consider the case in which, instead of making the core denser, we add links to the periphery. These two procedures of core and periphery thickening delineate a decision process in the placement of new links and allow us to conduct a scenario analysis that can be helpful in the comprehension and supervision of complex networks under the resilience perspective. The advantages of the two procedures, as well as their implications, are discussed in relation to both network effciency and node heterogeneity.
Consider the following process on a network: Each agent initially holds either opinion blue or red; then, in each round, each agent looks at two random neighbors and, if the two have the same opinion, the agent adopts it. This process is known as the 2-Choices dynamics and is arguably the most basic non-trivial opinion dynamics modeling voting behavior on social networks. Despite its apparent simplicity, 2-Choices has been analytically characterized only on restricted network classes---under assumptions on the initial configuration that establish it as a fast majority consensus protocol. In this work, we aim at contributing to the understanding of the 2-Choices dynamics by considering its behavior on a class of networks with core-periphery structure, a well-known topological assumption in social networks. In a nutshell, assume that a densely-connected subset of agents, the core, holds a different opinion from the rest of the network, the periphery. Then, depending on the strength of the cut between the core and the periphery, a phase-transition phenomenon occurs: Either the cores opinion rapidly spreads among the rest of the network, or a metastability phase takes place, in which both opinions coexist in the network for superpolynomial time. The interest of our result is twofold. On the one hand, by looking at the 2-Choices dynamics as a simplistic model of competition among opinions in social networks, our theorem sheds light on the influence of the core on the rest of the network, as a function of the cores connectivity toward the latter. On the other hand, we provide one of the first analytical results which shows a heterogeneous behavior of a simple dynamics as a function of structural parameters of the network. Finally, we validate our theoretical predictions with extensive experiments on real networks.
We study the diffusion of epidemics on networks that are partitioned into local communities. The gross structure of hierarchical networks of this kind can be described by a quotient graph. The rationale of this approach is that individuals infect those belonging to the same community with higher probability than individuals in other communities. In community models the nodal infection probability is thus expected to depend mainly on the interaction of a few, large interconnected clusters. In this work, we describe the epidemic process as a continuous-time individual-based susceptible-infected-susceptible (SIS) model using a first-order mean-field approximation. A key feature of our model is that the spectral radius of this smaller quotient graph (which only captures the macroscopic structure of the community network) is all we need to know in order to decide whether the overall healthy-state defines a globally asymptotically stable or an unstable equilibrium. Indeed, the spectral radius is related to the epidemic threshold of the system. Moreover we prove that, above the threshold, another steady-state exists that can be computed using a lower-dimensional dynamical system associated with the evolution of the process on the quotient graph. Our investigations are based on the graph-theoretical notion of equitable partition and of its recent and rather flexible generalization, that of almost equitable partition.
Intermediate-scale (or `meso-scale) structures in networks have received considerable attention, as the algorithmic detection of such structures makes it possible to discover network features that are not apparent either at the local scale of nodes and edges or at the global scale of summary statistics. Numerous types of meso-scale structures can occur in networks, but investigations of such features have focused predominantly on the identification and study of community structure. In this paper, we develop a new method to investigate the meso-scale feature known as core-periphery structure, which entails identifying densely-connected core nodes and sparsely-connected periphery nodes. In contrast to communities, the nodes in a core are also reasonably well-connected to those in the periphery. Our new method of computing core-periphery structure can identify multiple cores in a network and takes different possible cores into account. We illustrate the differences between our method and several existing methods for identifying which nodes belong to a core, and we use our technique to examine core-periphery structure in examples of friendship, collaboration, transportation, and voting networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
