Complex Networks & Their Applications X

Random neighbor sampling, or RN, is a method for sampling vertices with an average degree greater than the mean degree of the graph. It samples a vertex, then exchanges it for one of its neighbors which is assumed to be of higher degree. While considerable research has analyzed various aspects of RN, the extra cost of sampling a second vertex is typically not addressed. In this paper, we offer an analysis of RN from the perspective of cost. We define three separate costs, the cost of sampling a vertex, the cost of sampling a neighbor, and the cost of selecting a vertex (as opposed to discarding it in exchange for another). We introduce variations to RN, $$RV\!N$$ R V N which retains the first sampled vertex, and RN-RV and $$RV\!N$$ R V N -RV which are ‘hybrid’ methods that sample differently in two separate phases. We study all of these methods in terms of the costs we define. The cost-benefit analysis highlights the methods’ strengths and weaknesses, with a specific focus on their respective performances for finding high-degree vs. low-degree vertices. The analyses and results provide a far richer understanding of RN and open a new area of exploration for researching additional sampling methods that are best suited for cost-effectiveness in light of particular goals.

An important task in combating COVID-19 involves the quick and correct diagnosis of patients, which is not only critical to the patient’s prognosis, but can also help to optimize the configuration of hospital resources. This work aims to classify chest radiographic images to help the diagnosis and prognosis of patients with COVID-19. In comparison to images of healthy lungs, chest images infected by COVID-19 present geometrical deformations, like the formation of filaments. Therefore, fractal dimension is applied here to characterize the levels of complexity of COVID-19 images. Moreover, real data often contains complex patterns beyond physical features. Complex networks are suitable tools for characterizing data patterns due to their ability to capture the spatial, topological and functional relationship between the data. Therefore, a complex network-based high-level data classification technique, capable of capturing data patterns, is modified and applied to chest radiographic image classification. Experimental results show that the proposed method can obtain high classification precision on X-ray images. Still in this work, a comparative study between the proposed method and the state-of-the-art classification techniques is also carried out. The results show that the performance of the proposed method is competitive. We hope that the present work generates relevant contributions to combat COVID-19.

Complex networks are emerging in low-Earth-orbit, with many thousands of satellites set for launch over the coming decade. These data transfer networks vary based on spacecraft interactions with targets, ground stations, and other spacecraft. While constellations of a few, large, and precisely deployed satellites often produce simple, grid-like, networks. New small-satellite constellations are being deployed on an ad-hoc basis into various orbits, resulting in complex network topologies. By modelling these space systems as flow networks, the dominant eigenvectors of the adjacency matrix identify influential communities of ground stations. This approach provides space system designers with much needed insight into how differing station locations can better achieve alternative mission priorities and how inter-satellite links are set to impact upon constellation design. Maximum flow and consensus-based optimisation methods are used to define system architectures that support the findings of eigenvector-based community detection.

In real world data classification tasks, we always face the situations where the data samples of the normal cases present a well defined pattern and the features of abnormal data samples vary from one to another, i.e., do not show a regular pattern. Up to now, the general data classification hypothesis requires the data features within each class to present a certain level of similarity. Therefore, such real situations violate the classic classification condition and make it a hard task. In this paper, we present a novel solution for this kind of problems through a network approach. Specifically, we construct a core-periphery network from the training data set in such way that core node set is formed by the normal data samples and peripheral node set contains the abnormal samples of the training data set. The classification is made by checking the coreness of the testing data samples. The proposed method is applied to classify radiographic image for COVID-19 diagnosis. Computer simulations show promising results of the method. The main contribution is to introduce a general scheme to characterize pattern formation of the data “without pattern”.

We investigate networks formed by keywords in tweets and study their community structure. Based on datasets of tweets mined from over seven hundred political figures in the U.S. and Canada, we hypothesize that such Twitter keyword networks exhibit a small number of communities. Our results are further reinforced by considering via so-called pseudo-tweets generated randomly and using AI-based language generation software. We speculate as to the possible origins of the small community hypothesis and further attempts at validating it.

The recent speedy development of COVID-19 mRNA vaccines has underlined the importance of cross-border patent collaboration. This paper uses the latest edition of the REGPAT database from the OECD and constructs the co-applicant patent networks for the fields of biotechnology and pharmaceuticals. We identify the cross-border collaborative regional centres in these patent networks at NUTS3 level using a clustering comparison approach based on adjusted mutual information (AMI). In particular, we measure and compare the AMI scores of the clustering before and after arbitrarily removing cross-border links of a focal node against the default clustering defined by national borders. The region with the largest difference in AMI scores is identified as the most cross-border collaborative centre, hence the name of our measure, AMI gain. We find that our measure both correlates with and has advantages over the traditional measure betweenness centrality and a simple measure of foreign share.

As data increase in both size and complexity, it is essential to determine optimal solutions for processing and interacting with network representations by human analysts. In this paper, we explore different ways of growing networks from a small set of “seed” nodes to create tractable sub-networks for human analysis. In particular, we define a method for generating different network expansions for preference testing and statistical analysis in a paired-comparison task. To illustrate this method, we generate a range of expansions from a database of politically exposed persons and conduct the preference study with professional criminal network analysts. The resulting statistical analysis demonstrates an avoidance of purely random generated networks and preference for naive network expansion methods (depth-limited traversals based on one or two “hops” from the seed nodes) over more statistically rigorous methods (e.g., edge- and node-based sampling). From these results and inferential analysis, we propose practice considerations and define future research.

The study of preterm infants neuro-motor status can be performed by analyzing infants spontaneous movements. Nowadays, available automatic methods for assessing infants motion patterns are still limited. We present a novel pipeline for the characterization of infants spontaneous movements, which given RGB videos leverages on network analysis and NLP. First, we describe a body configuration for each frame considering landmark points on infants bodies as nodes of a network and connecting them depending on their proximity. Each configuration can be described by means of attributed graphettes. We identify each attributed graphette by a string, thus allowing to study videos as texts, i.e. sequences of strings. This allows us exploiting NLP methods as topic modelling to obtain interpretable representations. We analyze topics to describe both global and local differences in infants with normal and abnormal motion patters. We find encouraging correspondences between our results and evaluations performed by expert physicians.

We study political elite networks within a framework of signed tem-poral network to investigate the dynamics of coalition formation and polarization during the 2014 Indonesian General Elections. We construct the signed network of inferred relations of agreement or disagreement between Indonesian political ac-tors based on their opinion that is reported by news media during the election. For each temporal network, we detect communities by applying a community detection algorithm for signed networks to identify conflicting groups of political ac-tors, and characterize the identified groups based on party attributes. We visualize the networks and measure political tensions within and between clusters to examine the dynamics of polarization over time. We find that the coalition pattern is absent during the legislative election period, where political actors are more likely to group within their respective party clusters. The intensity of polarization be-tween clusters is relatively lower than the following two periods, with a downward trend of polarization ahead of the legislative election day. The cleavage line between coalition clusters begins to form in the presidential election period and lasts into the post-election period, where the emerged pattern resembles the configuration of party coalitions in the 2014 Indonesian Presidential Election. The process of coalition formation is accompanied by an increase in the intensity of polarization between coalition clusters.

This work proposes Field of Study networks as a novel network representation for use in scientometric analysis. We describe the formation of Field of Study (FoS) networks, which relate research topics according to the authors who publish in them, from corpora of articles where fields of study can be identified. FoS networks are particularly useful for the distant reading of large datasets of research papers, through the lens of exploring multidisciplinary science. To support this, we include case studies which explore multidisciplinary research in corpora of varying size and scope; namely, 891 articles relating to network science research and 166,000 COVID-19 related articles.

Public procurement fraud is a plague that produces significant economic losses in any state and society, but empirical studies to detect it in this area are still scarce. This article presents a review of the most recent literature on public procurement to identify techniques for fraud detection using Network Science. Applying the PRISMA methodology and using the Scopus and Web of Science repositories, we selected scientific articles and compared their results over a period from 2011 to 2021. Employing a compiled search string, we found cluster analysis and centrality measures as the most adopted techniques.

Today, many users are actively using Twitter to express their opinions and to share information. Thanks to the availability of the data, researchers have studied behaviours and social networks of these users. International migration studies have also benefited from this social media platform to improve migration statistics. Although diverse types of social networks have been studied so far on Twitter, social networks of migrants and natives have not been studied before. This paper aims to fill this gap by studying characteristics and behaviours of migrants and natives on Twitter. To do so, we perform a general assessment of features including profiles and tweets, and an extensive network analysis on the network. We find that migrants have more followers than friends. They have also tweeted more despite that both of the groups have similar account ages. More interestingly, the assortativity scores showed that users tend to connect based on nationality more than country of residence, and this is more the case for migrants than natives. Furthermore, both natives and migrants tend to connect mostly with natives.

This paper investigates the stability and evolution of the world stage of global science at the city level by analyzing changes in co-authorship network centrality rankings over time. Driven by the problem that there exists no consensus in the literature on how the spatial unit “city” should be defined, we first propose a new approach to delineate so-called scientific cities. On a high-quality Web of Science dataset of 21.5 million publications over the period 2008–2020, we study changes in centrality rankings of subsequent 3-year time-slices of scientific city co-authorship networks at various levels of impact. We find that, over the years, the world stage of global science has become more stable. Additionally, by means of a comparison with degree respecting rewired networks we reveal how new co-authorships between authors from previously unconnected cities more often connect ‘close’ cities in the network periphery.

Recent years have witnessed a rise in real-world data captured with rich structural information that can be conveniently depicted by multi-relational graphs. While inference of continuous node features across a simple graph is rather under-studied by the current relational learning research, we go one step further and focus on node regression problem on multi-relational graphs. We take inspiration from the well-known label propagation algorithm aiming at completing categorical features across a simple graph and propose a novel propagation framework for completing missing continuous features at the nodes of a multi-relational and directed graph. Our multi-relational propagation algorithm is composed of iterative neighborhood aggregations which originate from a relational local generative model. Our findings show the benefit of exploiting the multi-relational structure of the data in several node regression scenarios in different settings.

As the complexity of our food systems increases, they also become susceptible to unanticipated natural and human-initiated events. Commodity trade networks are a critical component of our food systems in ensuring food availability. We develop a generic data-driven framework to construct realistic agricultural commodity trade networks. Our work is motivated by the need to study food flows in the context of biological invasions. These networks are derived by fusing gridded, administrative-level, and survey datasets on production, trade, and consumption. Further, they are periodic temporal networks reflecting seasonal variations in production and trade of the crop. We apply this approach to create networks of tomato flow for two regions – Senegal and Nepal. Using statistical methods and network analysis, we gain insights into spatiotemporal dynamics of production and trade. Our results suggest that agricultural systems are increasingly vulnerable to attacks through trade of commodities due to their vicinity to regions of high demand and seasonal variations in production and flows.

Higher-order networks are efficient representations of sequential data. Unlike the classic first-order network approach, they capture indirect dependencies between items composing the input sequences by the use of memory-nodes. We focus in this study on the variable-order network model introduced in [10, 12]. Authors suggested that random-walk-based mining tools can be directly applied to these networks. We discuss the case of the PageRank measure. We show the existence of a bias due to the distribution of the number of representations of the items. We propose an adaptation of the PageRank model in order to correct it. Application on real-world data shows important differences in the achieved rankings.

We investigate a metric parameter “Leanness” of graphs which is a formalization of a well-known Fellow Travelers Property present in some metric spaces. Given a graph $$G=(V,E)$$ G = ( V , E ) , the leanness of G is the smallest $$\lambda $$ λ such that, for every pair of vertices $$x,y\in V$$ x , y ∈ V , all shortest (x, y)-paths stay within distance $$\lambda $$ λ from each other. We show that this parameter is bounded for many structured graph classes and is small for many real-world networks. We present efficient algorithms to compute or estimate this parameter and evaluate the performance of our algorithms on a number of real-world networks.

To characterize the “average” of a set of graphs, one can compute the sample Fréchet mean. We prove the following result: if we use the Hamming distance to compute distances between graphs, then the Fréchet mean of an ensemble of inhomogeneous random graphs is obtained by thresholding the expected adjacency matrix: an edge exists between the vertices i and j in the Fréchet mean graph if and only if the corresponding entry of the expected adjacency matrix is greater than 1/2. We prove that the result also holds for the sample Fréchet mean when the expected adjacency matrix is replaced with the sample mean adjacency matrix. This novel theoretical result has some significant practical consequences; for instance, the Fréchet mean of an ensemble of sparse inhomogeneous random graphs is the empty graph.

This work extends the bag-of-paths model [14] by introducing a weighting of the length of the paths in the network, provided by a Poisson probability distribution. The main advantage of this approach is that it allows to tune the mean path length parameter which is most relevant for the application at hand. Various quantities of interest, such as the probability of drawing a path from the bag of paths, or the join probability of sampling any path connecting two nodes of interest, can easily be computed in closed form from this model. In this context, a new distance measure between nodes of a network, considering a weighting factor on the length of the paths, is defined. Experiments on semi-supervised classification tasks show that the introduced distance measure provides competitive results compared to other state-of-the-art methods. Moreover, a new interpretation of the logarithmic communicability similarity measure [17] is proposed in terms of the new model.

We study the problem of score and rank monotonicity for spectral ranking methods, such as eigenvector centrality and PageRank, in the case of undirected networks. Score monotonicity means that adding an edge increases the score at both ends of the edge. Rank monotonicity means that adding an edge improves the relative position of both ends of the edge with respect to the remaining nodes. It is known that common spectral rankings are both score and rank monotone on directed, strongly connected graphs. We show that, surprisingly, the situation is very different for undirected graphs, and in particular that PageRank is neither score nor rank monotone.

Developing a tailor-made centrality measure for a given task requires domain and network analysis expertise, as well as time and effort. Automatically learning arbitrary centrality measures provided ground truth node scores is an important research direction. In this article, we propose a generic deep learning architecture for centrality learning that relies on the insight that arbitrary centrality measures can be computed using Routing Betweenness Centrality (RBC) and our new differentiable implementation of RBC. The proposed Learned Routing Centrality (LRC) architecture optimizes the routing function of RBC to fit the ground truth scores. Results show that LRC can learn multiple types of centrality indices more accurately than state-of-the-art.

This paper deals with ranking algorithms for signed graphs. We analyze the algebraic properties of the exponential ranking algorithm and suggest an alternative ranking scheme that is close to the exponential ranking in several respects, but which also enjoys the property of being linear. We discuss the properties of the introduced scheme and present both algebraic and numerical evidence that it is indeed very close to the exponential ranking.

The paper presents a new algorithm for updating PageRank on dynamic directed graphs after the addition of a node. The algorithm uses the expected value of the random surfer to calculate the score of the newly added node and nodes of the existing chain where the new node is added. The complexity of the algorithm for k updates is $$\mathcal {O}(k\times d_{avg})$$ O ( k × d avg ) . Extensive experiments have been performed on different synthetic and real-world networks. The experimental result shows that the rank generated by the proposed method is highly correlated with that of the benchmark algorithm of Power Iteration.

We propose an extension of the celebrated K-means algorithm for community detection in feature-rich networks. Our least-squares criterion leads to a straightforward extension of the conventional batch K-means clustering method as an alternating optimization strategy for the criterion. By replacing the innate squared Euclidean distance with cosine distance we effectively tackle the so-called curse of dimensionality. We compare our proposed methods using synthetic and real-world data with state-of-the-art algorithms from the literature. The cosine distance-based version appears to be the overall winner, especially at larger datasets.

Community finding algorithms are complex, often stochastic algorithms used to detect highly-connected groups of nodes in a graph. As with “black-box” machine learning models, these algorithms typically provide little in the way of explanation or insight into their outputs. In this research paper, inspired by recent work in explainable artificial intelligence (XAI), we look to develop post-hoc explanations for community finding, which are agnostic of the choice of algorithm. Specifically, we propose a new approach to identify features that indicate whether a set of nodes comprises a coherent community or not. We evaluate our methodology, which selects interpretable features from a longlist of candidates, in the context of three well-known community finding algorithms.

Heterogeneity characterises real-world networks, where nodes show a broad range of different topological features. However, nodes also tend to organise into communities – subsets of nodes that are sparsely inter-connected but are densely intra-connected (more than the network’s average connectivity). This means that nodes belonging to the same community are close to each other by some distance measure, such as the resistance distance, which is the effective distance between any pair of nodes considering all possible paths. In this work, we present automation (i.e., unsupervised) and missing accuracy tests for a recently proposed semi-supervised community detection algorithm based on the resistance distance. The accuracy testing involves quantifying our algorithm’s performance in terms of recovering known synthetic communities from benchmark networks, where we present results for Girvan-Newman and Lancichinetti-Fortunato-Radicchi networks. Our findings show that our algorithm falls into the class of fairly accurate performers.

The Italian academic community is an interesting case study of emerging collaborations among people that share interest in some topics. In this paper, we select and analyze three different research areas—defined by the Italian law “academic disciplines” (SSDs)—each with different topics and interests: computer engineering, mathematics and economics. Specifically, we first collect the data of the academic researchers belonging to these SSDs from Elsevier’s Scopus public database and create the co–authorship networks. Then, we study the topological characteristics and the existing communities for each network and compare them, highlighting differences and similarities.

Graph measures that express closeness or distance between nodes can be employed for graph nodes clustering using metric clustering algorithms. There are numerous measures applicable to this task, and which one performs better is an open question. We study the performance of 25 graph measures on generated graphs with different parameters. While usually measure comparisons are limited to general measure ranking on a particular dataset, we aim to explore the performance of various measures depending on graph features. Using an LFR graph generator, we create a dataset of 11780 graphs covering the whole LFR parameter space. For each graph, we assess the quality of clustering with k-means algorithm for each considered measure. Based on this, we determine the best measure for each area of the parameter space. We find that the parameter space consists of distinct zones where one particular measure is the best. We analyze the geometry of the resulting zones and describe it with simple criteria. Given particular graph parameters, this allows us to recommend a particular measure to use for clustering.

Targeting influential nodes in complex networks allows fastening or hindering rumors, epidemics, and electric blackouts. Since communities are prevalent in real-world networks, community-aware centrality measures exploit this information to target influential nodes. Researches show that they compare favorably with classical measures that are agnostic about the community structure. Although the diffusion process is of prime importance, previous studies consider mainly the famous Susceptible-Infected-Recovered (SIR) epidemic propagation model. This work investigates the consistency of previous analyses using the popular Linear Threshold (LT) propagation model, which characterizes many spreading processes in our real life. We perform a comparative analysis of seven influential community-aware centrality measures on thirteen real-world networks. Overall, results show that Community-based Mediator, Comm Centrality, and Modularity Vitality outperform the other measures. Moreover, Community-based Mediator is more effective on a tight budget (i.e., a small fraction of initially activated nodes), while Comm Centrality and Modularity Vitality perform better with a medium to a high fraction of initially activated nodes.

The problem of hiding a node inside of a network in the presence of an unauthorized crawler has been shown to be NP-complete. The available heuristics tackle this problem from mainly two perspectives: (1) the local immediate neighborhood of the target node (local perturbation models) and (2) the global structure of the graph (global perturbation models). While the objective of both is similar (i.e., decreasing the centrality of the target node), they vary substantially in their performance and efficiency; the global measures are computationally inefficient in the real-world scenarios, while the local perturbation methods deal with the problem of constrained performance. In this study, we propose a community-based heuristic, CoVerD, that retains both the computational efficiency of local methods and the superior performance of global methods in minimizing the target’s closeness centrality. Our experiments on five real-world networks show a significant increase in performance by using CoVerD against both BFS and DFS crawling attacks. In some instances, our algorithm successfully increased the crawler’s budget by 3 and 10 times compared to the next best-performing benchmark. The results of this study show the importance of the local community structure in preserving the privacy of the nodes in a network, and pave a promising path for designing scalable and effective network protection models.

Graph Neural Networks (GNNs) have been widely used to learn representations on graphs and tackle many real-world problems from a wide range of domains. In this paper we propose wsGAT, an extension of the Graph Attention Network (GAT) [24] layers, meant to address the lack of GNNs that can handle graphs with signed and weighted links, which are ubiquitous, for instance, in trust and correlation networks. We first evaluate the performance of our proposal by comparing against GCNII [6] in the weighed link prediction task, and against SGCN [8] in the link sign prediction task. After that, we combine the two tasks and show their performance on predicting the signed weight of links, and their existence. Our results on real-world networks show that models with wsGAT layers outperform the ones with GCNII and SGCN layers, and that there is no loss in performance when signed weights are predicted.

In this paper, we study how the observed quality of a network link prediction method applied to a part of a network can be further used for the analysis of the whole network. Namely, we first show that it can be determined for a part of the network which topological features of node pairs lead to a certain level of link prediction quality. Based on it, we construct a link predictability (prediction quality) classifier for the network links. This is further used in the other part of the network for controlling the link prediction quality typical for the method and the network. The actual link prediction method is not used then already. Experiments with synthetic and real-world networks show a good performance of the proposed pipeline. The source code, the datasets and the results related to our study are publicly available on GitHub.

Network science is a domain in which we focus on studying complex networks like social networks, chemical networks, computer networks, telecommunication networks, cognitive networks, semantic networks, and biological networks. In recent years, link prediction in complex networks has become an active research field because of its various real-world applications. In this paper, we present a novel algorithm for link prediction influenced by the concept of vertex entropy and ego networks. We used 12 real-world datasets to evaluate the performance of the novel algorithm. Results are compared with the 12 baseline algorithm based on 4 metrics AUC, Precision, Prediction-Power, and Precision@K. Experimental results show the effectiveness of the novel algorithm.

Evolutionary game theory reveals biological processes in populations and cooperative interactions with their neighbors. Game theory can be applied to the network evolution since social dilemma is observed in various scenarios. Recently, we investigated the link evolution using the hawk-dove game (HD) on the network system. In this model, players connected/disconnected with their neighbors based on their experiences and we found that the network structure varied depending on the time. Since a critical behavior was found in our model, we succeeded in producing a scale-free network from a random network. Here, we further investigate the population dynamics and its relation to a critical phenomenon using the above proposed model.

Organisational learning processes often exploit developed individual mental models in order to obtain shared mental models for the organisation by some form of unification or aggregation. The focus in this paper is on this aggregation process, which may depend on a number of contextual factors. It is shown how a second-order adaptive network model for organisation learning can be used to model this process of aggregation of individual mental models in a context-dependent manner.

In this paper, we focus on the popularity effect of the scientific collaboration process that popular authors have an advantage in making more publications. Standard network analysis has been used to analyze the scientific collaboration network. However, the standard network has limitations in explaining the scientific output by binary co-authorship relationships since papers have various numbers of authors. We propose a leading author model to understand the popularity effect mechanism while avoiding the use of the standard network structure. The estimation algorithm is presented to analyze the size of the popularity effect. Moreover, we can find influential authors through the estimated genius levels of authors by considering the popularity effect. We apply the proposed model to the real scientific collaboration data, and the results show positive popularity effects in all the collaborative systems. Furthermore, finding influential authors considering the genius level are discussed.

Small World networks, as defined by Watts and Strogatz, have a mixture of regular and random links. Inspired by Granovetter’s definition of a weak tie, a new metric is proposed that can be used to separate a network into regular and random sub-networks. It is shown that within certain constraints, a (modified) small world network can be factored with an accuracy of $$100\%$$ 100 % . The metric is shown to uncover interesting insights and factored networks can be used in downstream applications such as community finding and link prediction.

Random graph models play a central role in network analysis. The Chung-Lu model, which connects nodes based on their expected degrees, is of particular interest. It is widely used to generate null-graph models with expected degree sequences. In addition, these attachment probabilities implicitly define network measures such as modularity. Despite its popularity, practical methods for generating instances of Chung-Lu model-based graphs do relatively poor jobs in terms of accurately realizing many degree sequences. We perform a theoretical analysis of the Chung-Lu random graph model in order to understand this discrepancy. We approximate the expected output of a generated Chung-Lu random graph model with a linear system and use properties of this system to predict distribution errors. We provide bounds on the maximum proportion of nodes with a given degree that can be reliably produced by the model for both general and non-increasing distributions. We additionally provide an explicit inverse of our linear system and in cases where the inverse can provide a valid solution, we introduce a simple method for improving the accuracy of Chung-Lu graph generation. Our analysis serves as an analytic tool for determining the accuracy of Chung-Lu random graph generation as well as correcting errors under certain conditions.

We study the variation of the stochastic process that describes the temporal behavior of the average degree of the neighbors for a fixed node in the Barabási-Albert networks. It was previously known that the expected value of this random quantity grows logarithmically with the number of iterations. In this paper, we use the mean-field approach to derive difference stochastic equations, as well as their corresponding approximate differential equations, in order to find the dynamics of its variation in time. The noteworthy fact proved in this paper is that the variation of this process is bounded by a constant. This behavior is fundamentally different from the dynamics of variation in most known stochastic processes (e.g., the Wiener process), in which its value tends to infinity over time.

Complex systems, such as communication networks, generate thousands of new data points about the system state every minute. Even if faults are rare events, they can easily propagate, which makes it challenging to distinguish root causes of errors from effects among the thousands of highly correlated alerts appearing simultaneously in high volumes of data. In this context, the need for automated Root Cause Analysis (RCA) tools emerges, along with the creation of a causal model of the real system, which can be regarded as a digital twin. The advantage of such model is twofold: (i) it assists in reasoning on the system state, given partial system observations; and (ii) it allows generating labelled synthetic data, in order to benchmark causal discovery techniques or create previously unseen faulty scenarios (counterfactual reasoning). The problem addressed in this paper is the creation of a causal model which can mimic the behavior of the real system by encoding the appearance, propagation and persistence of faults through time. The model extends Structural Causal Models (SCMs) with the use of logical noisy-OR gates to incorporate the time dimension and represent propagation behaviors. Finally, the soundness of the approach is experimentally verified by generating synthetic alert logs and discovering both the structure and parameters of the underlying causal model.

In this paper, we address a problem of constructing weighted networks of earthquakes with multiple parent nodes, where the pairs of earthquakes with strong interaction are connected. To this end, by extending a representative conventional method based on the correlation-metric that produces an unweighted network with a single-parent node, we develop a method for constructing a network with multiple-parent nodes and assigning weight to each link by a link-weighting scheme called logarithmic-inverse-distance. In our experimental evaluation, we use an earthquake catalog that covers the whole of Japan, and select 24 major earthquakes which caused significant damage or casualties in Japan. In comparison to four different link-weighting schema, i.e., uniform, magnitude, inverse-distance, and normalized-inverse-distance, we evaluate the effectiveness of the constructed networks by our proposed method, in terms of the ranking accuracy based on the most basic centrality, i.e., weighted degree measure. As a consequence, we show that our proposed method works well, and then discuss the reasons why weighted networks with multiple-parent nodes can improve the ranking accuracy.

In this paper, we formulate a new problem of extracting motif-based node roles from a graph with edge uncertainty, where we first count roles for each node in each sampled graph, second calculate similarities between nodes in terms of role frequency and divide all nodes into clusters according to the similarity of roles. To achieve good accuracy of role extraction for uncertain graphs, a huge amount of graph sampling, role counting, similarity calculation, or clustering is needed. For efficiently extracting node-roles from a large-scale uncertain graph, we propose four ensemble methods and compare the similarity of results and efficiency. From the experiments using four different types of real networks with probabilities assigned to their edges, we confirmed that the graph-ensemble method is much more efficient in terms of execution time compared to other ensemble methods equipped with the state-of-the-art motif counting algorithm.

Graphlets, being the fundamental building blocks, are essential for understanding and analysing complex networks. The original notion of graphlets, however, is unable to encode edge attributes in many types of networks, especially in egocentric social networks. In this paper, we introduce a framework to embed edge type information in graphlets and generate a Typed-Edge Graphlets Degree Vector (TyE-GDV). Through applying the proposed method to a case study of chronic pain patients, we find that not only a patient’s social network structure could inform his/her perceived pain grade, but also particular types of social relationships, such as friends, colleagues and healthcare workers, are more important in understanding the effect of chronic pain. Further, we demonstrate that including TyE-GDV as additional features leads to significant improvement in a typical machine learning task.

We present a temporal network analysis of militarized interstate dispute (MID) data from 1992 to 2014. MIDs progress through a series of incidents, each ranging from threats to uses of military force by one state to another. We model these incidents as a temporal conflict network, where nodes denote states and directed edges denote incidents. We analyze temporal motifs or subgraphs in the conflict network to uncover the patterns by which different states engage in and escalate conflicts with each other. We find that different types of temporal motifs appear in the network depending on the time scale being considered (days to months) and the year of the conflict. The most frequent 3-edge temporal motifs at a 1-week time scale correspond to different variants of two states acting against a third state, potentially escalating the conflict. Temporal motifs with reciprocation, where a state acts in response to a previous incident, tend to occur only over longer time scales (e.g. months). We also find that both the network’s degree and temporal motif distributions are extremely heavy tailed, with a small number of states being involved in many conflicts.

Bi-pattern mining has been previously introduced to mine attributed networks in which nodes may have two roles, as bi-partite or directed networks. A bi-pattern is then made of a pair of attribute patterns, and has a pair of support sets to figure the occurrences of the bi-pattern. Restricted bi-pattern mining has then been introduced to enforce both components of a bi-pattern to share part of their attribute content, so leading to a reduced bi-pattern space. The definition of a new closure operator allows then to enumerate such closed restricted bi-patterns. The presentation was theoretical and no experiments were provided. Our contribution is practical, it displays experiments comparing efficiency and results of restricted bi-pattern mining to their unrestricted bi-pattern mining counterparts.

The problem of finding paths in temporal graphs has been recently considered due to its many applications. In this paper we consider a variant of the problem that, given a vertex-colored temporal graph, asks for a path whose vertices have distinct colors and include the maximum number of colors. We study the approximation complexity of the problem and we provide an inapproximability lower bound. Then we present a heuristic for the problem and an experimental evaluation of our heuristic, both on synthetic and real-world graphs.

One of the most common approaches to the analysis of dynamic networks is through time-window aggregation. The resulting representation is a sequence of static networks, i.e. the snapshot graph. Despite this representation being widely used in the literature, a general framework to evaluate the soundness of snapshot graphs is still missing. In this article, we propose two scores to quantify conflicting objectives: Stability measures how much stable the sequence of snapshots is, while Fidelity measures the loss of information compared to the original data. We also develop a technique of targeted filtering of the links, to simplify the original temporal network. Our framework is tested on datasets of proximity and face-to-face interactions.

We study network properties of networks evolving in time based on optimal transport principles. These evolve from a structure covering uniformly a continuous space towards an optimal design in terms of optimal transport theory. At convergence, the networks should optimize the way resources are transported through it. As the network structure shapes in time towards optimality, its topological properties also change with it. The question is how do these change as we reach optimality. We study the behavior of various network properties on a number of network sequences evolving towards optimal design and find that the transport cost function converges earlier than network properties and that these monotonically decrease. This suggests a mechanism for designing optimal networks by compressing dense structures. We find a similar behavior in networks extracted from real images of the networks designed by the body shape of a slime mold evolving in time.

Dynamic or temporal networks enable representation of time-varying edges between nodes. Conventional adjacency-based data structures used for storing networks such as adjacency lists were designed without incorporating time. When used to store temporal networks, such structures can be used to quickly retrieve all edges between two sets of nodes, which we call a node-based slice, but cannot quickly retrieve all edges that occur within a given time interval, which we call a time-based slice. We propose a hybrid data structure for storing temporal networks with timestamped edges, including instantaneous edges such as messages on social media and edges with duration such as phone calls. Our hybrid structure stores edges in both an adjacency dictionary, enabling rapid node-based slices, and an interval tree, enabling rapid time-based slices. We evaluate our hybrid data structure on many real temporal network data sets and find that they achieve much faster slice times than adjacency-based baseline structures with only a modest increase in creation time and memory usage.

We introduce a Markov Modulated Process (MMP) to describe human mobility. We represent the mobility process as a time-varying graph, where a link specifies a connection between two nodes (humans) at any discrete time step. Each state of the Markov chain encodes a certain modification to the original graph. We show that our MMP model successfully captures the main features of a random mobility simulator, in which nodes moves in a square region. We apply our MMP model to human mobility, measured in a library.

Reactions to social pain and the behavioral strategies adopted as a consequence of it are a complex and adaptive phenomenon that leads to major consequences to a person’s social functioning and overall well-being. As such behavioral strategies are something that change over time and are difficult to explain by simple linear correlations, a model such as this one is useful to the goal of providing a more nuanced understanding of the phenomena and the way that it changes dynamically over time, potentially leading to richer theoretical predictions and potential new directions for research.

This paper investigates the impact of monetary rewards on behavioral strategies and the quality of posts in consumer generated media (CGM). In recent years, some CGM platforms have introduced monetary rewards as an incentive to encourage users to post articles. However, the impact of monetary rewards on users has not been sufficiently clarified. Therefore, to investigate the impact of monetary rewards, we extend the SNS-norms game, which models SNSs based on the evolutionary game theory, by incorporating the model of monetary rewards, the users’ preferences for them, and their efforts for article quality. The results of the experiments on several types of networks indicate that monetary rewards promote posting articles but significantly reduce the article quality. Particularly, when the value of the monetary reward is small, it significantly reduces the utilities of all the users owing to a decrease in quality. We also found that individual user preferences for monetary rewards had a clear difference in their behavior.

In a networked anagram game, each team member is given a set of letters and members collectively form as many words as possible. They can share letters through a communication network in assisting their neighbors in forming words. There is variability in behaviors of players, e.g., there can be large differences in numbers of letter requests, of replies to letter requests, and of words formed among players. Therefore, it is of great importance to understand uncertainty and variability in player behaviors. In this work, we propose versatile uncertainty quantification (VUQ) of behaviors for modeling the networked anagram game. Specifically, the proposed methods focus on building contrastive models of game player behaviors that quantify player actions in terms of worst, average, and best performance. Moreover, we construct agent-based models and perform agent-based simulations using these VUQ methods to evaluate the model building methodology and understand the impact of uncertainty. We believe that this approach is applicable to other networked games.

One of the challenges facing artificial intelligence research today is designing systems capable of utilizing systematic reasoning to generalize to new tasks. The Abstraction and Reasoning Corpus (ARC) measures such a capability through a set of visual reasoning tasks. In this paper we report incremental progress on ARC and lay the foundations for two approaches to abstraction and reasoning not based in brute-force search. We first apply an existing program synthesis system called DreamCoder to create symbolic abstractions out of tasks solved so far, and show how it enables solving of progressively more challenging ARC tasks. Second, we design a reasoning algorithm motivated by the way humans approach ARC. Our algorithm constructs a search graph and reasons over this graph structure to discover task solutions. More specifically, we extend existing execution-guided program synthesis approaches with deductive reasoning based on function inverse semantics to enable a neural-guided bidirectional search algorithm. We demonstrate the effectiveness of the algorithm on three domains: ARC, 24-Game tasks, and a ‘double-and-add’ arithmetic puzzle.

This work presents a network-based data-driven study of the combination of factors that contribute to success in mountaineering. It simultaneously examines the effects of individual factors such as age, gender, experience etc., as well as expedition-wide factors such as number of camps, ratio of sherpas to paying climbers etc. Specifically, it combines the two perspectives through a multiscale network model, i.e., a network of network of climbers within each expedition at the finer scale, and an expedition similarity network at the coarser scale. The latter is represented as a multiplex network where layers encode different factors. The analysis reveals that chances of failure to summit due to fatigue, altitude or logistical problems, drastically reduce when climbing with people they have climbed with before, especially for experienced climbers. Additionally, centrality indicates that individual traits of youth and oxygen use while ascending are the strongest drivers of success. Further, the learning of network projections enables computation of correlations between intra-expedition networks and corresponding expedition success rates. Of expedition-wide factors, the expedition size and total time layers are found to be strongly correlated with success rate. Lastly, community detection on the expedition-similarity network reveals distinct communities where a difference in success rates naturally emerges amongst the communities.

Data from surveys administered after Hurricane Sandy provide a wealth of information that can be used to develop models of evacuation decision-making. We use a model based on survey data for predicting whether or not a family will evacuate. The model uses 26 features for each household including its neighborhood characteristics. We augment a 1.7 million node household-level synthetic social network of Miami, Florida with public data for the requisite model features so that our population is consistent with the survey-based model. Results show that household features that drive hurricane evacuations dominate the effects of specifying large numbers of families as “early evacuators” in a contagion process, and also dominate effects of peer influence to evacuate. There is a strong network-based evacuation suppression effect from the fear of looting. We also study spatial factors affecting evacuation rates as well as policy interventions to encourage evacuation.

We define a model for the evolution of linguistic convention in a population of agents embedded on a network, and consider the effects of topology on the population-level language dynamics. Individuals are subject to evolutionary forces that over time result in the adoption of a shared language throughout the population. The differences in convergence time to a common language and that language’s communicative efficiency under different underlying social structures and population sizes are examined. We find that shorter average path lengths contribute to a faster convergence and that the final payoff of languages is unaffected by the underlying topology. Compared to models for the emergence of linguistic convention based on self-organization, we find similarities in the effects of average path lengths, but differences in the role of degree heterogeneity.

Interaction networks are generally much less homophilic than affiliation networks, accommodating for many more cross-cutting links. By statistically assigning a political valence to users from their follower ties, and by further contrasting interaction and affiliation on Twitter (quotes and retweets) within specific discursive events, namely quote trees, we describe a variety of cross-cutting patterns which significantly nuance the traditional “echo chamber” narrative.

We use social network analysis to model the trade networks that connect each of the United States to the rest of the world in an effort to capture trade shocks and supply chain disruptions resulting from the COVID-19 pandemic and, more specifically, to capture how such disruptions propagate through those networks. The results show that disruptions will noticeably move along industry connections, spreading in specific patterns. Our results are also consistent with past work that shows that non-pharmaceutical policy interventions have had limited impact on trade flows.

Small and medium enterprises (SME) are crucial for economy and have a higher exposure rate to default than large corporates. In this work, we address the problem of predicting the default of an SME. Default prediction models typically only consider the previous financial situation of each analysed company. Thus, they do not take into account the interactions between companies, which could be insightful as SMEs live in a supply chain ecosystem in which they constantly do business with each other. Thereby, we present a novel method to improve traditional default prediction models by incorporating information about the insolvency situation of customers and suppliers of a given SME, using a graph-based representation of SME supply chains. We analyze its performance and illustrate how this proposed solution outperforms the traditional default prediction approaches.

“Success” of firms in venture capital markets is hard to define, and its determinants are still poorly understood. We build a bipartite network of investors and firms in the healthcare sector, describing its structure and its communities. Then, we characterize “success” by introducing progressively more refined definitions, and we find a positive association between such definitions and the centrality of a company. In particular, we are able to cluster funding trajectories of firms into two groups capturing different “success” regimes and to link the probability of belonging to one or the other to their network features (in particular their centrality and the one of their investors). We further investigate this positive association by introducing scalar as well as functional “success” outcomes, confirming our findings and their robustness.

Diffusion processes are well known linear dynamical systems. However, a different kind of dynamical solutions emerge when the speed of diffusion is dependent on the sign of the gradient variable that is diffused through the graph. In this case, we move into a nonlinear dynamical system where solutions would depend on the differential speed of diffusion, the topological structure of the graph and the initial values of the gradient variable.We show an example in a real complex network: we construct a network of US Boards of Directors, where nodes are boards, and links are interlocking directorates. We show that the proportion of women on each board follows a diffusion process, where changes depend of the gradient of this proportion to adjacent boards. Furthermore, we show that the diffusion is asymmetric, with diffusion slower(faster) when the board has a lower(higher) proportion of women than neighbor boards.

We introduce an agent-based model of localised perceptions of the gender and racial wage gap in Random Geometric Graph type networks that result from economic homophily independent of gender/race. Thereby, agents estimate inequality using a composite signal consisting of local information from their personal neighbourhood and the actual global wage gap. This can replicate the underestimation of the gender or racial wage gap that empirical studies find and the well-documented fact that the underprivileged perceive the wage gap to be higher on average with less bias. Calibration by a recent Israeli sample suggests that women place much more weight on the (correct) global signal than men, in line with the hypothesis that people who are adversely affected by a wage gap listen more carefully to global information about the issue. Hence, (educational) interventions about the global state of gender and racial inequality are promising, especially if they target the privileged.

Understanding the drivers of economic growth is one of the fundamental questions in Economics. While the role of the factors of production—capital and labor—is well understood, the mechanisms that underpin Total Factor Productivity (TFP) are not fully determined. A number of heterogeneous studies point to the creation and transmission of knowledge, factor supply, and economic integration as key aspects; yet a need for a systematic and unifying framework still exists. Both capital and labor are embedded into a complex network structure through global supply chains and international migration, and it has been shown that the structure of global trade plays an important role in economic growth. Additionally, recent research has established a link between types of social capital and different network centralities. In this paper we explore the role of these measures of social capital as drivers of the TFP. By leveraging the EORA Multi Regional Input Output and the UN International Migration databases we build the complex network representation for capital and labor respectively. We compile a panel data set covering 155 economies and 26 years. Our results indicate that social capital in the factors of production network significantly drives economic output through TFP.

We analyse the transaction networks of four representative ERC-20 tokens that run on top of the public blockchain Ethereum and can be used as collateral in DeFi: Ampleforth (AMP), Basic Attention Token (BAT), Dai (DAI) and Uniswap (UNI). We use complex network analysis to characterize structural properties of their transaction networks. We compute their preferential attachment and we investigate how critical code-controlled nodes (smart contracts, SC) executed on the blockchain are in comparison to human-owned nodes (externally owned accounts, EOA), which are be controlled by end users with public and private keys or by off-blockchain code. Our findings contribute to characterise these new financial networks. We use three network dismantling strategies on the transaction networks to analyze the criticality of smart contract and known exchanges nodes as opposed to EOA nodes. We conclude that smart contract and known exchanges nodes play a structural role in holding up these networks, theoretically designed to be distributed but in reality tending towards centralisation around hubs. This sheds new light on the structural role that smart contracts and exchanges play in Ethereum and, more specifically, in Decentralized Finance (DeFi) networks and casts a shadow on how much decentralised these networks really are. From the information security viewpoint, our findings highlight the need to protect the availability and integrity of these hubs.

In this study, synchronization of complex networks subject to impulses with average characteristics is investigated. Specifically, the ideas of average impulse interval and average impulse delay are applied to analyze the effect of delayed impulses on synchronization of complex networks. Further, the new concept of average impulse exponential gain is proposed to globally describe the multiple impulses whose magnitude is allowed to be time-varying. Interestingly, it is shown that the delay in impulses can possess synchronizing impact on the synchronization of complex networks with such multiple delayed impulses. Finally, an numerical example is presented to illustrate the validness of the derived results.

The Internet and the Web can be described as huge networks of connected computers, connected web pages, or connected users. Analyzing link retrieval methods on the Internet and the Web as examples of complex networks is of particular importance. The recovery of complex networks is an important issue that has been extensively used in various fields. Much work has been done to measure and improve the stability of complex networks during attacks. Recently, many studies have focused on the network recovery strategies after the attack. Predicting the appropriate redundant links in a way that the network can be recovered at the lowest cost and fastest time after attacks or interruptions will be critical in a disaster. In addition, real-world networks such as the World Wide Web are no exception, and many attacks are made on hyperlinks between web pages, and the issue of predicting redundant hyperlinks on this World Wide Web is also very important.In this paper, different kinds of attack strategies are provided and some retrieval strategies based on link prediction methods are proposed to recover the hyperlinks after failure or attack. Besides that, a new link prediction method based on the hyperbolic geometry of the complex network is proposed to retrieve redundant hyperlinks and the numerical simulation reveals its superiority that the state-of-the-art algorithms in recovering the attacked hyperlinks especially in the case of attacks based on edge betweenness strategy.

Reinforcement learning has shown much success in games such as chess, backgammon and Go [21, 22, 24]. However, in most of these games, agents have full knowledge of the environment at all times. In this paper, we describe a deep learning model in which agents successfully adapt to different classes of opponents and learn the optimal counter-strategy using reinforcement learning in a game under partial observability. We apply our model to $$\mathsf {FlipIt}$$ FlipIt [25], a two-player security game in which both players, the attacker and the defender, compete for ownership of a shared resource and only receive information on the current state of the game upon making a move. Our model is a deep neural network combined with Q-learning and is trained to maximize the defender’s time of ownership of the resource. Despite the noisy information, our model successfully learns a cost-effective counter-strategy outperforming its opponent’s strategies and shows the advantages of the use of deep reinforcement learning in game theoretic scenarios. We also extend $$\mathsf {FlipIt}$$ FlipIt to a larger action-spaced game with the introduction of a new lower-cost move and generalize the model to n-player $$\mathsf {FlipIt}$$ FlipIt .

In this paper, we study the problem of opponent strategy inference from observations of information diffusion in voting dynamics on complex networks. We demonstrate that, by deploying resources of an active controller, it is possible to influence the information dynamics in such a way that opponent strategies can be more easily uncovered. To this end, we use the framework of maximum likelihood estimation and the Fisher information to construct confidence intervals for opponent strategy estimates. We then design heuristics for optimally deploying resources with the aim of minimizing the variance of estimates. In the first part of the paper, we focus on inferring an opponent strategy at a single node. Here, we derive optimal resource allocations, finding that, for low controller budget, resources should be focused on the inferred node and, for large budget, on the inferred nodes’ neighbours. In the second part, we extend the setting to inferring opponent strategies over the entire network. We find that opponents are the harder to detect the more heterogeneous networks are, even with optimal targeting.

Complex networks are robust to random failures; but not always to targeted attacks. The resilience of complex networks towards different node targeted attacks are studied immensely in the literature. Many node attack strategies were also proposed, and their efficiency was compared. However, in each of these proposals, the scientists used different measures of efficiency. So, it doesn’t seem easy to compare them and choose the one most suitable for the system under examination. Here, we review the main results from the literature on centrality based node attack strategies. Our focus is only on the works on undirected and unweighted networks. We want to highlight the necessity of a more realistic measure of attack efficiency.

Gionis et al. have already proposed a greedy algorithm and some heuristics for the opinion maximization problem. Unlike their approach, we adopt mathematical programming to solve the opinion maximization problem on specific classes of networks. We find that on directed acyclic graphs, opinion influence between nodes will not cycle, but would spread outwards from influencers. Based on such an insight, we model the problem as a mixed integer programming (MIP) problem and relax the MIP to a linear program (LP). With MIP, we obtain optimal solutions for the opinion maximization problem and derive approximation solutions with LP randomized rounding algorithms. We conduct experiments for one LP randomized rounding algorithm and give an analysis of the approximation ratio for the other LP randomized rounding algorithm.