Date: Thu, 9 May 2024 | Total: 6
A wide range of tasks in exploratory network analysis and machine learning, such as clustering network populations or identifying anomalies in temporal graph streams, require a measure of the similarity between two graphs. To provide a meaningful data summary for downstream scientific analyses, the graph similarity measures used in these unsupervised settings must be principled, interpretable, and capable of distinguishing meaningful overlapping network structure from statistical noise at different scales of interest. Here we derive a family of graph mutual information measures that satisfy these criteria and are constructed using only fundamental information theoretic principles. Our measures capture the information shared among networks according to different encodings of their structural information, with our mesoscale mutual information measure allowing for network comparison under any specified network coarse-graining. We test our measures in a range of applications on real and synthetic network data, finding that they effectively highlight intuitive aspects of network similarity across scales in a variety of systems.
Possibility of reaching a consensus in social systems with strong initial fragmentation is one of the most interesting issues in sociopysics. It is also intriguing what the dynamics of such processes is. To address those problems, we performed computer simulations using well-established models of social opinion formation, namely the voter, Sznajd, and Latan\'e models. We investigated opinion dynamics in cases where the initial number of opinions is very large, equal to the number of actors (the voter and Latan\'e models) or when every second actor has their own opinion (Sznajd model), with some variations on the update schemes, lattice topologies, effective ranges of interaction, and information noise levels. For all considered models, the number of opinions assumed by the actors is finally almost always reduced to only one. However, while the voter and Latan\'e models exhibit a power-law time decrease in the number of opinions, the Sznajd model follows a complex three-stage behavior. We also demonstrated that the mean/median time of reaching the consensus scales with system size according to a power law for voter and Sznajd models, while for the Latan\'e model this increase is even faster. Our results show that in the studied models the consensus is possible, provided that a long enough and model-dependent time to reach this state is available.
A common method for delineating urban and suburban boundaries is to identify clusters of spatial units that are highly interconnected in a network of commuting flows, each cluster signaling a cohesive economic submarket. It is critical that the clustering methods employed for this task are principled and free of unnecessary tunable parameters to avoid unwanted inductive biases while remaining scalable for high resolution mobility networks. Here we systematically assess the benefits and limitations of a wide array of Stochastic Block Models (SBMs)$\unicode{x2014}$a family of principled, nonparametric models for identifying clusters in networks$\unicode{x2014}$for delineating urban spatial boundaries with commuting data. We find that the data compression capability and relative performance of different SBM variants heavily depends on the spatial extent of the commuting network, its aggregation scale, and the method used for weighting network edges. We also construct a new measure to assess the degree to which community detection algorithms find spatially contiguous partitions, finding that traditional SBMs may produce substantial spatial discontiguities that make them challenging to use in general for urban boundary delineation. We propose a fast nonparametric regionalization algorithm that can alleviate this issue, achieving data compression close to that of unconstrained SBM models while ensuring spatial contiguity, benefiting from a deterministic optimization procedure, and being generalizable to a wide range of community detection objective functions.
We investigate the collective behavior of a system of social agents subject to the competition between two mass media influences considered as external fields. We study under what conditions either of two mass media with different intensities can impose its message to the majority. In addition to a collective state dominated by the stronger mass media and a disordered phase, we characterize two nontrivial effects as the parameters of the system are varied: (i) the appearance of a majority sharing the state of the weaker mass media, and (ii) the emergence of an alternative ordering in a state different from those of either media. We explore the dependence of both phenomena on the topology of the network of interactions. We show that the presence of long-range interactions rather than random connections is essential for the occurrence of both effects. The model can be extended to include multiple mass media and we illustrate it by considering three mass media fields acting on the system. Nontrivial collective behaviors persist for some ranges of parameters: the weakest mass media can convince the majority, and the system can spontaneously order against all applied fields.
Networks where each node has one or more associated numerical values are common in applications. This work studies how summary statistics used for the analysis of spatial data can be applied to non-spatial networks for the purposes of exploratory data analysis. We focus primarily on Moran-type statistics and discuss measures of global autocorrelation, local autocorrelation and global correlation. We introduce null models based on fixing edges and permuting the data or fixing the data and permuting the edges. We demonstrate the use of these statistics on real and synthetic node-valued networks.
The problem of community detection in multi-layer undirected networks has received considerable attention in recent years. However, practical scenarios often involve multi-layer bipartite networks, where each layer consists of two distinct types of nodes. Existing community detection algorithms tailored for multi-layer undirected networks are not directly applicable to multi-layer bipartite networks. To address this challenge, this paper introduces a novel multi-layer degree-corrected stochastic co-block model specifically designed to capture the underlying community structure within multi-layer bipartite networks. Within this framework, we propose an efficient debiased spectral co-clustering algorithm for detecting nodes' communities. We establish the consistent estimation property of our proposed algorithm and demonstrate that an increased number of layers in bipartite networks improves the accuracy of community detection. Through extensive numerical experiments, we showcase the superior performance of our algorithm compared to existing methods. Additionally, we validate our algorithm by applying it to real-world multi-layer network datasets, yielding meaningful and insightful results.