ترغب بنشر مسار تعليمي؟ اضغط هنا

Analytical Formulation of the Block-Constrained Configuration Model

61   0   0.0 ( 0 )
 نشر من قبل Giona Casiraghi
 تاريخ النشر 2018
والبحث باللغة English
 تأليف Giona Casiraghi




اسأل ChatGPT حول البحث

We provide a novel family of generative block-models for random graphs that naturally incorporates degree distributions: the block-constrained configuration model. Block-constrained configuration models build on the generalised hypergeometric ensemble of random graphs and extend the well-known configuration model by enforcing block-constraints on the edge generation process. The resulting models are analytically tractable and practical to fit even to large networks. These models provide a new, flexible tool for the study of community structure and for network science in general, where modelling networks with heterogeneous degree distributions is of central importance.



قيم البحث

اقرأ أيضاً

Advancing our understanding of human behavior hinges on the ability of theories to unveil the mechanisms underlying such behaviors. Measuring the ability of theories and models to predict unobserved behaviors provides a principled method to evaluate their merit and, thus, to help establish which mechanisms are most plausible. Here, we propose models and develop rigorous inference approaches to predict strategic decisions in dyadic social dilemmas. In particular, we use bipartite stochastic block models that incorporate information about the dilemmas faced by individuals. We show, combining these models with empirical data on strategic decisions in dyadic social dilemmas, that individual strategic decisions are to a large extent predictable, despite not being rational. The analysis of these models also allows us to conclude that: (i) individuals do not perceive games according their game-theoretical structure; (ii) individuals make decisions using combinations of multiple simple strategies, which our approach reveals naturally.
Mesoscopic pattern extraction (MPE) is the problem of finding a partition of the nodes of a complex network that maximizes some objective function. Many well-known network inference problems fall in this category, including, for instance, community d etection, core-periphery identification, and imperfect graph coloring. In this paper, we show that the most popular algorithms designed to solve MPE problems can in fact be understood as special cases of the maximum likelihood formulation of the stochastic block model (SBM), or one of its direct generalizations. These equivalence relations show that the SBM is nearly universal with respect to MPE problems.
As new instances of nested organization --beyond ecological networks-- are discovered, scholars are debating around the co-existence of two apparently incompatible macroscale architectures: nestedness and modularity. The discussion is far from being solved, mainly for two reasons. First, nestedness and modularity appear to emerge from two contradictory dynamics, cooperation and competition. Second, existing methods to assess the presence of nestedness and modularity are flawed when it comes to the evaluation of concurrently nested and modular structures. In this work, we tackle the latter problem, presenting the concept of textit{in-block nestedness}, a structural property determining to what extent a network is composed of blocks whose internal connectivity exhibits nestedness. We then put forward a set of optimization methods that allow us to identify such organization successfully, both in synthetic and in a large number of real networks. These findings challenge our understanding of the topology of ecological and social systems, calling for new models to explain how such patterns emerge.
Maximum entropy null models of networks come in different flavors that depend on the type of constraints under which entropy is maximized. If the constraints are on degree sequences or distributions, we are dealing with configuration models. If the d egree sequence is constrained exactly, the corresponding microcanonical ensemble of random graphs with a given degree sequence is the configuration model per se. If the degree sequence is constrained only on average, the corresponding grand-canonical ensemble of random graphs with a given expected degree sequence is the soft configuration model. If the degree sequence is not fixed at all but randomly drawn from a fixed distribution, the corresponding hypercanonical ensemble of random graphs with a given degree distribution is the hypersoft configuration model, a more adequate description of dynamic real-world networks in which degree sequences are never fixed but degree distributions often stay stable. Here, we introduce the hypersoft configuration model of weighted networks. The main contribution is a particular version of the model with power-law degree and strength distributions, and superlinear scaling of strengths with degrees, mimicking the properties of some real-world networks. As a byproduct, we generalize the notions of sparse graphons and their entropy to weighted networks.
A preferential attachment model for a growing network incorporating deletion of edges is studied and the expected asymptotic degree distribution is analyzed. At each time step $t=1,2,ldots$, with probability $pi_1>0$ a new vertex with one edge attach ed to it is added to the network and the edge is connected to an existing vertex chosen proportionally to its degree, with probability $pi_2$ a vertex is chosen proportionally to its degree and an edge is added between this vertex and a randomly chosen other vertex, and with probability $pi_3=1-pi_1-pi_2<1/2$ a vertex is chosen proportionally to its degree and a random edge of this vertex is deleted. The model is intended to capture a situation where high-degree vertices are more dynamic than low-degree vertices in the sense that their connections tend to be changing. A recursion formula is derived for the expected asymptotic fraction $p_k$ of vertices with degree $k$, and solving this recursion reveals that, for $pi_3<1/3$, we have $p_ksim k^{-(3-7pi_3)/(1-3pi_3)}$, while, for $pi_3>1/3$, the fraction $p_k$ decays exponentially at rate $(pi_1+pi_2)/2pi_3$. There is hence a non-trivial upper bound for how much deletion the network can incorporate without loosing the power-law behavior of the degree distribution. The analytical results are supported by simulations.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا