Complex Networks XV

We consider the following problem: we have a high-resolution street network of a given city, and low-resolution measurements of traffic within this city. We want to associate to each measurement the set of streets corresponding to the observed traffic. To do so, we take benefit of specific properties of these data to match measured links to links in the street network. We propose several success criteria for the obtained matching. They show that the matching algorithm generally performs very well, and they give complementary ways to detect data discrepancies that makes any matching highly dubious.

We propose a pipeline for identifying important entities from intelligence reports that constructs a knowledge graph, where nodes correspond to entities of fine-grained types (e.g. traffickers) extracted from the text and edges correspond to extracted relations between entities (e.g. cartel membership). The important entities in intelligence reports then map to central nodes in the knowledge graph. We introduce a novel method that extracts fine-grained entities in a few-shot setting (few labeled examples), given limited resources available to label the frequently changing entity types that intelligence analysts are interested in. It outperforms other state-of-the-art methods. Next, we identify challenges facing previous evaluations of zero-shot (no labeled examples) methods for extracting relations, affecting the step of populating edges. Finally, we explore the utility of the pipeline: given the goal of identifying important entities, we evaluate the impact of relation extraction errors on the identification of central nodes in several real and synthetic networks. The impact of these errors varies significantly by graph topology, suggesting that confidence in measurements based on automatically extracted relations should depend on observed network features.

In this article we extend the Marketing Mix Diffusion (MMD) model to inhomogenous networks (i.e. complex networks of arbitrary topology). The (Homogenous) MMD model is an innovation diffusion model, similar to the Bass model, which includes four decision variables (the 4Ps of Marketing: Product, Price, Place, Promotion). We introduce the Inhomogenous MMD (IMMD) model and we conduct two separate experiments: one based on simulation and another one relying on empirical evidence. The simulation study compares the behavior of the IMMD model with the classic Bass diffusion model. Results suggest that the classic Bass model is able to represent the IMMD curves quite well in most cases. The IMMD is more general and capable of representing extreme scenarios. The empirical study focuses on the geographic diffusion of mobile broadband technology in Japan, combining adoption data with a spatial network of municipalities. The in-sample performance of the model is comparable to the existing methods, which suggests a good explanatory power of the IMMD model.

The study of polarization has gained increasing attraction in the past decades. Since observing both opinions and interactions is challenging, epistemic programs such as agent-based models have been proposed as a means to assessing the systemic consequences of social psychology mechanisms. Most results in agent-based models for opinion dynamics have focused on individual opinion constructs and pairwise interactions, with a few works treating group effects as constraints. Meanwhile, a tradition in social sciences has been putting emphasis on how group configuration affects individual behavior. In this work, we introduce a new model for accounting for both pairwise interactions in which actors observe and update opinions, and individual perception of the evolving configuration of groups that make up the population in which they are embedded. Through experiments, we show that pairwise interactions which are different depending on whether they are in-group or out-group, has quantifiable impact on the resulting polarization of a population. In particular, the tolerance toward out-group opinions is shown to have a strong impact on the resulting polarization. Our model produces and accounts for polarized states resulting from group consolidation and fragmentation.

Motifs are overrepresented and statistically significant sub-patterns in a network, whose identification is relevant to uncover its underlying functional units. Recently, its extraction has been performed on higher-order networks, but due to the complexity arising from polyadic interactions, and the similarity with known computationally hard problems, its practical application is limited. Our main contribution is a novel approach for hyper-subgraph census and higher-order motif discovery, allowing for motifs with sizes 3 or 4 to be found efficiently, in real-world scenarios. It is consistently an order of magnitude faster than a baseline state-of-art method, while using less memory and supporting a wider range of base algorithms.

Bilateral trade relationships have been under increased scrutiny by the economic literature for their relevant role in influencing economic growth and, more in general, for their impact in the geopolitical sphere. Many studies try to understand the determinants and dynamics of trade flows. However, only a few have leveraged the growing availability of granular data to consistently analyze specific sectors of the economy and address the challenges posed by contemporary issues, such as climate change, for which understanding the temporal trade dynamics can be critical in the rush toward the green transition. This work aims to fill this gap by implementing a module to model and directly preprocess the most updated granular trade data in a network and by proposing a simple yet effective methodology to identify the evolving dynamics of temporal networks. As a use case, we focus on trades related to semiconductors and minerals relevant to energy storage, namely lithium and graphite, both relevant sectors for the energy transition, and, employing our novel approach, we uncover recent trends in these markets.

Recently there has been increased interest in fitting generative graph models to real-world networks. In particular, Bläsius et al. have proposed a framework for systematic evaluation of the expressivity of random graph models. We extend this framework to Geometric Inhomogeneous Random Graphs (GIRGs). This includes a family of graphs induced by non-metric distance functions which allow capturing more complex models of partial similarity between nodes as a basis of connection—as well as homogeneous and non-homogeneous feature spaces. As part of the extension, we develop schemes for estimating the multiplicative constant and the long-range parameter in the connection probability. Moreover, we devise an algorithm for sampling Minimum-Component-Distance GIRGs whose runtime is linear both in the number of vertices and in the dimension of the underlying geometric space. Our results provide evidence that GIRGs are more realistic candidates with respect to various graph features such as closeness centrality, betweenness centrality, local clustering coefficient, and graph effective diameter, while they face difficulties to replicate higher variance and more extreme values of graph statistics observed in real-world networks.

This paper delves into the intricate world of Russian culinary traditions, focusing on three iconic dishes: Olivier salad, vinegret, and okroshka. Utilizing a network analysis approach, we scrutinized 460 Olivier salad ingredient lists, alongside 97 vinegret and 127 okroshka ingredient lists, collected through online surveys. The findings highlight the vast diversity and regional variations in ingredient selection, emphasizing the adaptability of these dishes across different communities. The Olivier salad analysis, in particular, unveiled two main ingredient clusters, underscoring a dichotomy between vegetable-herb-meat combinations and a more protein-centric selection, which can be attributed to both cultural influences and individual preferences. The comprehensive ingredient list network analysis further corroborated these findings, revealing underlying patterns in ingredient pairing and ingredient list construction. By mapping out the complex relationships between ingredients and ingredient lists, this study provides valuable insights into the culinary practices surrounding these beloved Russian dishes, contributing to the broader understanding of food culture and tradition in Russia and beyond.

The patterns and dynamics that govern the flow of concepts and the association of information for various scientific domains, are not well understood in the realm of knowledge evolution and organisation. To that end, we look at using concept networks to capture the associations between these concepts as a domain grows. We compare concept networks as they grow for scientific domains, sci-fi literature, common news topics and science news, using Quantum Spectral Jensen-Shannon Divergence, to evaluate how consistent their network structures are at their early stages. We find that everyday concept networks tend to be more consistent with each other, whereas scientific networks are less consistent and we discuss the potential factors influencing the structures of these networks.

Graph embedding has become an increasingly important technique for analyzing graph-structured data. By representing nodes in a graph as vectors in a low-dimensional space, graph embedding enables efficient graph processing and analysis tasks like node classification, link prediction, and visualization. In this paper, we propose and provide proof of convergence for a novel graph embedding paradigm where nodes are assumed to possess mass and a kinematic-based force-directed model is applied to calculate embedding gradients. Our proposed force-directed graph embedding method utilizes the steady acceleration kinematic equations to embed nodes in a way that preserves graph topology and structural features. This method simulates a set of customized attractive and repulsive forces between all node pairs with respect to their hop distance. These forces are then used in Newton’s second law to obtain the acceleration of each node. The method is intuitive, parallelizable, and highly scalable. We evaluate our method on several graph analysis tasks and show that it achieves competitive performance compared to state-of-the-art unsupervised embedding techniques.

Epidemic spread prediction and prevention have been of paramount significance for safeguarding the public health and quality of life. However, the adoption of the appropriate safety measures and actions should also take into account other societal challenges, such as the impact on the local economy or the psychological strain on its inhabitants. Recent approaches for preventing an epidemic spread have led to the adoption of rather aggressive strategies with significantly negative side-effects. In this work we address the aforementioned issue by developing a dynamic and data-driven prevention strategy, using modern graph machine learning predictive models. This strategy imposes more realistic assumptions about the pandemic spread and the underlying network structure, while also minimizing the negative side-effects. Finally, the experimental evaluation of our novel architecture for the predictive model demonstrates that we significantly outperform existing methods.

In the field of node representation learning the task of interpreting latent dimensions has become a prominent, well-studied research topic. The contribution of this work focuses on appraising the interpretability of another rarely-exploited feature of node embeddings increasingly utilised in recommendation and consumption diversity studies: inter-node embedded distances. Introducing a new method to measure how understandable the distances between nodes are, our work assesses how well the proximity weights derived from a network before embedding relate to the node closeness measurements after embedding. Testing several classical node embedding models, our findings reach a conclusion familiar to practitioners albeit rarely cited in literature—the matrix factorisation model SVD is the most interpretable through 1, 2 and even higher-order proximities.

The robustness of networks plays a crucial role in various applications. Network dismantling, the process of strategically removing nodes or edges to maximize damage, is a known NP-hard problem. While heuristics for node removal exist, edge network dismantling, especially in real-world scenarios like power grids or transportation networks, remains underexplored. This paper introduces eGDM-RL, a novel framework for edge dismantling based on Geometric Deep Learning and Reinforcement Learning. Unlike previous approaches, this method demonstrates superior performance in terms of the Area Under the dismantling Curve (AUC) with low computational complexity. The proposed model, utilizing a Graph Attention Network (GAT) and a Deep Q-value Network (DQN), outperforms traditional methods such as those based on edge betweenness. Experimental results on real-world networks validate the effectiveness of the proposed eGDM-RL framework, offering insights into critical edge removal for practical applications.

With the increasing incentives to improve public transportation service, as a means for addressing the current climate crisis, sociologists and urban planners, alike, have stressed the importance of improving transit service for all. This entails ensuring that vulnerable demographics are not neglected as urban planning shifts towards more sustainable modes. Research in transport justice reveals the concentration of economically vulnerable individuals in the urban core, granting better access to transit service due to the abundance of urban resources. However, these same works also point to the exclusionary effect that transit systems have on the lower-income individuals that reside in the periphery, while also highlighting how constraints on the neighbourhoods that public transit serves, can limit individuals’ residential options. In this work, we develop a framework, using open-source data and tools, to explore the trends of socioeconomic transit inequalities with regards to neighbourhood characteristics. Specifically, for 9 cities in the USA, we define neighbourhoods based on their built environment (BE) characteristics. Then, we assess general transit characteristics across the BE groups, revealing better transit service for BE groups with higher density, diversity, and design. We incorporate socioeconomic characteristics of each neighbourhood, revealing how overlooking BE characteristics can obscure socioeconomic disparities in transit service. Finally, we compare our empirical findings to a null model that strips away the socioeconomic structure across neighbourhoods, showing the constraints that transit systems impose on residential locations. Ultimately, this work aims to motivate approaching transport poverty from a built environment perspective, to develop a more nuanced understanding of how transit service can be improved and how transit disparities in accessibility may impact individuals’ day-to-day experiences.