Complex Networks and Their Applications XI

The Artificial Benchmark for Community Detection graph (ABCD) is a random graph model with community structure and power-law distribution for both degrees and community sizes. The model generates graphs with similar properties as the well-known LFR one, and its main parameter $$\xi $$ can be tuned to mimic its counterpart in the LFR model, the mixing parameter $$\mu $$ . In this paper, we investigate various theoretical asymptotic properties of the ABCD model. In particular, we analyze the modularity function, arguably, the most important graph property of networks in the context of community detection. Indeed, the modularity function is often used to measure the presence of community structure in networks. It is also used as a quality function in many community detection algorithms, including the widely used Louvain algorithm.

We investigate the statistical learning of nodal attribute distributions in homophily networks using random walks. Attributes can be discrete or continuous. A generalization of various existing canonical models, based on preferential attachment is studied, where new nodes form connections dependent on both their attribute values and popularity as measured by degree. We consider several canonical attribute agnostic sampling schemes such as Metropolis-Hasting random walk, versions of node2vec (Grover and Leskovec 2016) that incorporate both classical random walk and non-backtracking propensities and propose new variants which use attribute information in addition to topological information to explore the network. The performance of such algorithms is studied on both synthetic networks and real world systems, and its dependence on the degree of homophily, or absence thereof, is assessed.

We present a more powerful heuristic algorithm for the NP-complete problem of finding a minimum size subset of edges in an unbalanced signed graph G whose ‘+’/‘−’ labels can be flipped to balance G. Our algorithm finds a minimal flipping edge-set, starting with a given spanning tree T of G, by considering both the edges not in T and those in T because flipping a tree-edge can sometimes balance multiple fundamental unbalanced cycles at the same time. This can give a much smaller minimal flipping edge-set than the current algorithm where only the edges not in T are considered for flipping.

The Mantel Test, discovered in the 1960s, determines whether two distance metrics on a graph are related. We describe DC-RST, an algorithm to accelerate a key step of a network science statistical computation associated with DimeCost, an approach that is faster the Mantel Test. DC-RST is a parallel, divide-and-conquer algorithm to compute a random spanning tree of a complete graph on n vertices. Relative to an implementation of Wilson’s sequential random-walk algorithm, on a system with 48 cores, DC-RST was up to 4X faster when first creating random partitions and up to 20X faster without this sub-step. DC-RST is shown to be a suitable replacement for Wilson’s sequential algorithm through a combination of theoretical and statistical results.

Large-scale dense networks are very parvasive in various fields such as communication, social analytics, architecture, bio-metrics, etc. Thus, the need to build a compact version of the networks allowing their analysis is a matter of great importance. One of the main solutions to reduce the size of the network while maintaining its characteristics is backbone extraction techniques. Two types of methods are distinguished in the literature: similar nodes are gathered and merged in coarse-graining techniques to compress the network, while filter-based methods discard edges and nodes according to some statistical properties. In this paper, we propose a filtering-based approach which is based on the community structure of the network. The so-called “Acquaintance-Overlapping Backbone (AOB)” is a stochastic method which select overlapping nodes and the most connected nodes of the network. Experimental results show that the AOB is more effective in preserving relevant information as compared to some alternative methods.

Random graphs play a central role in network analysis. The Chung-Lu random graph model is one particularly popular model, which connects nodes according to their desired degrees to form a specific degree distribution in expectation. Despite its popularity, the standard Chung-Lu graph generation algorithms are susceptible to significant degree sequence errors when generating simple graphs. In this manuscript, we suggest multiple methods for improving the accuracy of Chung-Lu graph generation by computing node weights which better recreate the desired output degree sequence. We show that each of our solutions offer a significant improvement in degree sequence accuracy.

Interpersonal synchrony is associated with better interpersonal affiliation. No matter how well-affiliated people are, interruptions or transitions in synchrony rebound to occur. One might intuitively expect that transitions in synchrony negatively affect affiliation or liking. Empirical evidence, however, suggests that time periods with interruptions in synchrony may favor affiliation or liking even more than time periods without interruptions in synchrony. This paper introduces a controlled adaptive network model to explain how persons’ affiliation might benefit from transitions in synchrony over and above mean levels of synchrony. The adaptive network model was evaluated in a series of simulation experiments for two persons with a setup in which a number of scenarios were encountered in different (time) episodes. Our controlled adaptive network model may serve as a foundation for more realistic virtual agents with regard to synchrony transitions and their role in affiliation.

Ego-centric networks are an important class of networks to represent a particular node’s connections to its neighbors. This work aims at providing an efficient method to represent an ego-centric network so that all neighboring nodes are scattered on the surface of the unit sphere uniformly. Such uniformity is not just a simple space-filling distribution with maximum Euclidean distance among nodes, but with the consideration of existing edges among these nodes and without overlapping of node clusters. Our proposed method is a three-step method that partitions the spherical surface associated to a criterion on the edge-to-node ratio, then scatters the nodes on the respective subspace according to the relationship between nodes and modularity. To compute efficiently, the particle swarm optimization method is employed in all three steps to allocate the respective points. We show the connection between our space-filling distribution of points on a spherical surface to the minimum energy design on a two-dimensional flat plane with a specific gradient. We provide a demonstration on allocating nodes of an ego-centric network of 50 nodes, and some distance statistics show the good performance of our method when compared to four state-of-the-art methods via self-organizing maps and force-driven approaches.

In hyperbolic geometric networks the vertices are embedded in a latent metric space and the edge probability depends on the hyperbolic distance between the nodes. These models allows to produce networks with high clustering and scale-free degree distribution, where the coordinates of the vertices abstract their centrality and similarity. Based on the principles of hyperbolic models, in this paper we introduce the Hyperbolic Geometric Block Model, which yields highly clustered, scale-free networks while preserving the desired group mixing structure. We additionally study a parametric network model whose edge probability depends on both the distance in an explicit euclidean space and the distance in a latent geometric space. Through extensive simulations on a stylized city of 10K inhabitants, we provide experimental evidence of the robustness of the HGBM model and of the possibility to combine a latent and an explicit geometry to produce data-driven social networks that exhibit many of the main features observed in empirical networks.

Complex networks appear naturally in many real-world situations. A power law is generally a good fit for their degree distribution. The popular Barabasi-Albert model (BA) combines growth and preferential attachment to model the emergence of the power law. One builds a network by adding new nodes that preferentially link to high-degree nodes in the network. One can also exploit random walks. In this case, the network growth is determined by choosing parent vertices by sequential random walks. The BA model’s main drawback is that the sample networks’ clustering coefficient is low, while typical real-world networks exhibit a high clustering coefficient. Indeed, nodes tend to form highly connected groups in real-world networks, particularly social networks. In this paper, we introduce a Biased Random Walk model with two parameters allowing us to tune the degree distribution exponent and the clustering coefficient of the sample networks. This efficient algorithm relies on local information to generate more realistic networks reproducing known real-world network properties.

In weighted graphs the shortest path between two nodes is often reached through an indirect path, out of all possible connections, leading to structural redundancies which play key roles in the dynamics and evolution of complex networks. We have previously developed a parameter-free, algebraically-principled methodology to uncover such redundancy and reveal the distance backbone of weighted graphs, which has been shown to be important in transmission dynamics, inference of important paths, and quantifying the robustness of networks. However, the method was developed for undirected graphs. Here we expand this methodology to weighted directed graphs and study the redundancy and robustness found in nine networks ranging from social, biomedical, and technical systems. We found that similarly to undirected graphs, directed graphs in general also contain a large amount of redundancy, as measured by the size of their (directed) distance backbone. Our methodology adds an additional tool to the principled sparsification of complex networks and the measure of their robustness.

It has been experimentally shown that communities in social networks tend to have a core-periphery topology. However, there is still a limited understanding of the precise structure of core-periphery communities in social networks including the connectivity structure and interaction rates between agents. In this paper, we use a game-theoretic approach to derive a more precise characterization of the structure of core-periphery communities.

The Artificial Benchmark for Community Detection graph (ABCD) is a random graph model with community structure and power-law distribution for both degrees and community sizes. The model generates graphs with similar properties as the well-known LFR one, and its main parameter $$\xi $$ can be tuned to mimic its counterpart in the LFR model, the mixing parameter $$\mu $$ . In this paper, we extend the ABCD model to include potential outliers. We perform some exploratory experiments on both the new ABCD+o model as well as a real-world network to show that outliers posses some desired, distinguishable properties.

This paper studies the novel problem of influence-based community deception. Tackling this problem amounts to devising tools to protect the users of a community from being discovered by community detection algorithms. The novel setting considers networks that have both edge directions and models the influence of nodes as edge weights. We present a deception strategy based on modularity. We conducted an experimental evaluation that shows the feasibility of our proposal.

A recurring graph analysis task is to rank nodes based on their relevance to overlapping communities of shared metadata attributes (e.g. the interests of social network users). To achieve this, approaches often start with a few example community members and employ graph filters that rank nodes based on their structural proximity to the examples. Choosing between well-known filters typically involves experiments on existing graphs, but their efficacy is known to depend on the structural relations between community members. Therefore, we argue that employed filters should be determined not during algorithm design but at runtime, upon receiving specific graphs and example nodes to process. To do this, we split example nodes into training and validation sets and either perform supervised selection between well-known filters, or account for granular graph dynamics by tuning parameters of the generalized graph filter form with a novel optimization algorithm. Experiments on 27 community node ranking tasks across three real-world networks of various sizes reveal that runtime algorithm selection selects near-best AUC and NDCG among a list of 8 popular alternatives, and that parameter tuning yields similar or improved results in all cases.

Community detection is a challenging research problem, especially in dynamic networks, since in this case communities cannot remain stable as they evolve. In evolving networks new communities may emerge and existing communities may disappear, grow or shrink. There are many cases where someone is more interested in the evolution of a particular community, to which an important node belongs, rather than in the global partitioning of a dynamic network. However, due to the drifting problem where one community can evolve into a completely different one, it is difficult to track the evolution of communities. Our aim is to identify the community that contains a node of particular importance, called anchor, and its evolution over time. The framework we propose circumvents the identity problem by allowing the anchor to define the core of the relevant community partially or fully. Preliminary experiments with synthetic datasets demonstrate the positive aspects of the proposed framework in identifying communities with high accuracy.

Most popular algorithms for community detection in graphs have one serious drawback, namely, they are heuristic-based and in many cases are unable to find a near-optimal solution. Moreover, their results tend to exhibit significant volatility. These issues might be solved by a proper initialization of such algorithms with some carefully chosen partition of nodes. In this paper, we investigate the impact of such initialization applied to the two most commonly used community detection algorithms: Louvain and Leiden. We use a partition obtained by embedding the nodes of the graph into some high dimensional space of real numbers and then running a clustering algorithm on this latent representation. We show that this procedure significantly improves the results. Proper embedding filters unnecessary information while retaining the proximity of nodes belonging to the same community. As a result, clustering algorithms ran on these embeddings merge nodes only when they are similar with a high degree of certainty, resulting in a stable and effective initial partition.

In community detection, datasets often suffer a sampling bias for which nodes which would normally have a high affinity appear to have zero affinity. This happens for example when two affine users of a social network were not exposed to one another. Community detection on this kind of data suffers then from considering affine nodes as not affine. To solve this problem, we explicitly model the (non-) exposure mechanism in a Bayesian community detection framework, by introducing a set of additional hidden variables. Compared to approaches which do not model exposure, our method is able to better reconstruct the input graph, while maintaining a similar performance in recovering communities. Importantly, it allows to estimate the probability that two nodes have been exposed, a possibility not available with standard models.

Community detection of temporal (time-evolving) bipartite networks is challenging because it can be performed either on the temporal bipartite network, or on various projected networks, composed of only one type of nodes, via diverse community detection algorithms. In this paper, we aim to systematically design detection methods addressing both network choices and community detection algorithms, and to compare the community structures detected by different methods. We illustrate our methodology by using a telecommunications network as an example. We find that three methods proposed identify evident community structures: one is performed on each snapshot of the temporal network, and the other two, in temporal projections. We characterise the community structures detected by each method by an evaluation network in which the nodes are the services of the telecommunications network, and the weight of the links between them are the number of snapshots that both services were assigned to the same community. Analysing the evaluation networks of the three methods reveals the similarity and difference among these methods in identifying common node pairs or groups of nodes that often belong to the same community. We find that the two methods that are based on the same projected network identify consistent community structures, whereas the method based on the original temporal bipartite network complements this vision of the community structure. Moreover, we found a non-trivial number of node pairs that belong consistently to the same community in all the methods applied.

In the context of textual analysis, network-based procedures for topic detection are gaining attention as an alternative to classical topic models. Network-based procedures are based on the idea that documents can be represented as word co-occurrence networks, where topics are defined as groups of strongly connected words. Although many works have used network-based procedures for topic detection, there is a lack of systematic analysis of how different design choices, such as the building of the word co-occurrence matrix and the selection of the community detection algorithm, affect the final results in terms of detected topics. In this work, we present the results obtained by analysing a widely used corpus of news articles, showing how and to what extent the choices made during the design phase affect the results.

Community detection in networks is extensively studied from a structural perspective, but very few works characterize communities with respect to dynamics on networks. We propose a generic framework based on Moore-Shannon network reliability for defining and discovering communities with respect to a variety of dynamical processes. This approach extracts communities in directed edge-weighted networks which satisfy strong connectivity properties as well as strong mutual influence between pairs of nodes through the dynamical process. We apply this framework to food networks. We compare our results with modularity-based approach, and analyze community structure across commodities, evolution over time, and with regard to dynamical system properties.

In adversarial networks, edges correspond to negative interactions such as competition or dominance. We introduce a new type of node called a low-key leader in adversarial networks, distinguished by contrasting the centrality measures of CON score and PageRank. We present a novel hypothesis that low-key leaders are ubiquitous in adversarial networks and provide evidence by considering data from real-world networks, including dominance networks in 172 animal populations, trading networks between G20 nations, and Bitcoin trust networks. We introduce a random graph model that generates directed graphs with low-key leaders.

Often, due to prohibitively large size or to limits to data collecting APIs, it is not possible to work with a complete network dataset and sampling is required. A type of sampling which is consistent with Twitter API restrictions is uniform edge sampling. In this paper, we propose a methodology for the recovery of two fundamental network properties from an edge-sampled network: the degree distribution and the triangle count (we estimate the totals for the network and the counts associated with each edge). We use a Bayesian approach and show a range of methods for constructing a prior which does not require assumptions about the original network. Our approach is tested on two synthetic and two real datasets with diverse degree and triangle count distributions.

Group interactions occur frequently in social settings, yet their properties beyond pairwise relationships in network models remain unexplored. In this work, we study homophily, the nearly ubiquitous phenomena wherein similar individuals are more likely than random to form connections with one another, and define it on simplicial complexes, a generalization of network models that goes beyond dyadic interactions. While some group homophily definitions have been proposed in the literature, we provide theoretical and empirical evidence that prior definitions mostly inherit properties of homophily in pairwise interactions rather than capture the homophily of group dynamics. Hence, we propose a new measure, k-simplicial homophily, which properly identifies homophily in group dynamics. Across 16 empirical networks, k-simplicial homophily provides information uncorrelated with homophily measures on pairwise interactions. Moreover, we show the empirical value of k-simplicial homophily in identifying when metadata on nodes is useful for predicting group interactions, whereas previous measures are uninformative.

Graph isomorphism is a problem for which there is no known polynomial-time solution. The more general problem of computing graph similarity metrics, graph edit distance or maximum common subgraph, is NP-hard. Nevertheless, assessing (dis)similarity between two or more networks is a key task in many areas, such as image recognition, biology, chemistry, computer and social networks. In this article, we offer a statistical answer to the following questions: (a) “Are networks $$G_1$$ and $$G_2$$ similar?”, (b) “How different are the networks $$G_1$$ and $$G_2$$ ?” and (c) “Is $$G_3$$ more similar to $$G_1$$ or $$G_2$$ ?”. Our comparisons begin with the transformation of each graph into an all-pairs distance matrix. Our node-node distance, Jaccard distance, has been shown to offer an accurate reflection of the graph’s connectivity structure. We then model these distances as probability distributions. Finally, we use well-established statistical tools to gauge the (dis)similarities in terms of probability distribution (dis)similarity. This comparison procedure aims to detect (dis)similarities in connectivity structure and community structure in particular, not in easily observable graph characteristics, such as degrees, edge counts or density. We validate our hypothesis that graphs can be meaningfully summarized and compared via their node-node distance distributions, using several synthetic and real-world graphs. Empirical results demonstrate its validity and the accuracy of our comparison technique.

Alon et al. [1] investigated the following 2-player zero-sum game on a connected graph G: tree player chooses a spanning tree T of G, while edge player chooses an edge e of G. The payoff to the edge player is defined by a function $$\textrm{cost}(T,e)$$ . It is a natural continuation of their work is to consider the case when both players are a tree player. This also leads us to the problem of intersection of random spanning trees, that is the number of common edges of two spanning trees of G chosen uniformly at random. In this paper we derive a lower bound for the minimum expected intersection and using bootstrap simulations we determine the empirical mean value for synthetic and real networks. Experiments show that for random model networks there is no significant difference between the two value. On the other hand, interestingly, for some real networks the observed empirical mean intersection highly differs from the minimum expected. Our finding may provide a new perspective of investigating real small-world networks and gives some new insights on the structure of them.

One of the interesting tasks in social network analysis is detecting network nodes’ roles in their interactions. The first problem is discovering such roles, and the second is detecting the discovered roles in the network. Role detection, i.e., assigning a role to a node, is a classification task. Our paper addresses the second problem and uses three roles (classes) for classification. These roles are based only on the structural properties of the neighborhood of a given node and use the previously published non-symmetric relationship between pairs of nodes for their definition. This paper presents transductive learning experiments using graph neural networks (GNN) to show that excellent results can be obtained even with a relatively small sample size for training the network.

The Mean Hitting Time is a fundamental structural measure of random walks on networks with many applications ranging from epidemic diffusion on networks to fluctuations in stock prices. It measures the mean expected time for a random walker to reach all the source-destination pair nodes in the network. Previous research shows that it scales linearly with the network size for small-world sparse networks. Here, we calculate the Mean Hitting Time for large real-work complex networks and investigate how it scales with the q-subdivision operation used to grow the network. Indeed, this operation is essential in modeling realistic networks with small-world, scale-free and fractal characteristics. We use the Eigenvalues and eigenvectors of the normalized adjacency matrix of the initial network G to calculate the Hitting Time $$T_{ij}$$ between nodes i and j. We consider two complex real-world networks to analyze the evolution of the Mean Hitting Time as the networks grow with the q-subdivision. Results show that the Mean Hitting Time increases linearly with the value of q. This work provides insight into the design of realistic networks with small Mean Hitting Time.

Two typical characteristics of networks are average degree and density. Both characteristics are related, but using the second one does not provide easily interpretable information when analyzing differently sized networks. This paper deals with the measurement of network density with the possibility of comparing networks of different sizes. We point out the problems of the classical approach and, in response, introduce a new measure called $$\Delta $$ -density. The theoretical background of $$\Delta $$ -density is accompanied by a practical application example. We use five real networks with temporal information in the experiments to analyze the evolution of $$\Delta $$ -density.

Network controllability and its robustness has been widely studied. However, analytical methods to calculate network controllability with respect to node removals are currently lacking. This paper develops methods, based upon generating functions for the in- and out-degree distributions, to approximate the minimum number of driver nodes needed to control directed networks, during random and targeted node removals. By validating the proposed methods on synthetic and real-world networks, we show that our methods work very well in the case of random node removals and reasonably well in the case of targeted node removals, in particular for moderate fractions of attacked nodes.

Realization of highly tolerant networks against malicious attacks is an important issue, since many real-world networks are extremely vulnerable to attacks. Thus, we investigate the optimal robustness of connectivity against attacks on networks in changing degree distribution ranging from power-law to exponential or narrower ones. It is numerically found that the smaller variances of degree distributions lead to higher robustness in this range. Our results will provide important insights toward optimal robustness against attacks in changing degree distributions.

We study the problem of determining suitable investments in improving the robustness of complex systems comprising many component systems with an aim of minimizing the (time) average costs to system operators. The problem is formulated as an optimization problem that is nonconvex and challenging to solve for large systems. We propose two approaches to finding a good solution to the optimization problem: the first approach is based on a gradient method and finds a local optimizer. The second approach makes use of a convex relaxation of the original problem and provides both a lower bound on the optimal value and a feasible point. The lower bound can be used to bound the optimality gap of the solutions obtained by our methods. We provide numerical results to demonstrate the effectiveness of the proposed approaches.

Real-world infrastructures are often subject to random failures or intentional attacks that can significantly impact their robustness and hence many processes taking place on them. In this paper, we focus on the robustness of complex networks by proposing a link addition strategy for improving the network robustness. The approach exploits the incremental computation of the Moore-Penrose pseudoinverse matrix to efficiently compute the effective graph resistance when a new link is added to the network. Experiments on both real-world and synthetic data sets show that the strategy provides a good trade-off between a low percentage error of effective graph resistance with respect to the exhaustive search and the simulation time needed to obtain the optimal link.

Graph robustness upon node failures state-of-art is huge. However, not enough is known on the effects of centrality metrics ranking after graph perturbations. To fill this gap, our aim is to quantify how much small graph perturbations will affect the centrality metrics. Thus, we considered two type of probabilistic failure models (i.e., Uniform and Best Connected), a fraction $$\tau $$ of nodes under attack, with $$0 < \tau \le 1$$ , and three popular centrality metrics (i.e., Degree, the Eigenvector and the Katz centrality). We discovered that in the Uniform model the amount of change in the adjacency matrix due to a perturbation is not significantly affected when $$\tau $$ is small even with a quite high failure probability (i.e., $$p\le 85\%$$ ) and that the Eigenvector centrality is the most susceptible metric to deformation respect to the others herein analysed; whereas, in the Best Connected model, the amount of perturbation is proportional to $$\tau $$ .

The widely used characterization of scale-free networks as “robust-yet-fragile” originates primarily from experiments on instances generated by preferential attachment. According to this characterization, scale-free networks are more robust against random failures but more fragile against targeted attacks when compared to random networks of the same size. Here, we consider a more appropriate baseline by requiring that the random networks match not only the size but also the inherent minimum degree of preferential-attachment networks they are compared with. Under this more equitable condition, we can (1) prove that random networks are almost surely robust against any vertex removal strategy and (2) show through extensive experiments that scale-free networks generated by preferential attachment are not particularly robust against random failures.

In complex networks, network-dismantling aims at finding an optimal set of nodes (or edges) such that the removal of the set from the network will lead to the disintegration of the network, that is, the size of the giant/largest connected component is not bigger than a specific threshold (for instance, $$1\%$$ of the original network size). Existing algorithms addressing this topic can be divided into two closely related but different categories: vertex separator-oriented algorithms and edge separator-oriented algorithms. There has been a lot of research on these two categories, respectively. However, to the best of our knowledge, less attention has been paid to the relation between the vertex separator and edge separator. In this paper, we studied the separator transformation (ST) problem between the separator of the vertexes and edges. We approximated the transformation from edge separator to vertex separator using Vertex Cover algorithm, while approximated the transformation from vertex separator to edge separator using an Explosive Percolation (EP) approach. Moreover, we further analyzed the results of the vertex-edge separator transformation through the explosive percolation method in detail. The transformation problem in network-dismantling opens up a new direction for understanding the role of the vital nodes set and edges set as well as the vulnerability of complex systems.

Unparalleled advances in information technology have resulted in the virtualization of the workplace, as well as in a surge in non-traditional work arrangements based on short-term contracts (“gigs”). Work that is done remotely through online platforms may be hidden by technology. Thus, how could we possibly access information about the social network of workers? What are the business and social values hidden in workers’ underlying informal social networks? Here, we propose applying methods from complex network analysis to have an overview of data from a Brazilian food-delivery company. We present the steps used to make the inference of a social network that relates delivery men according to their co-location patterns. Hence, the obtained network offers a valuable framework to explore, in the future, questions related to the role of informal social networks in the spreading of innovations and the coordination of behaviors and business strategies.

This paper studies the concept of sectoral integration of energy systems from a network perspective. In the energy arena, the transition towards a cleaner use of energy has led to a series of changes in how we consume energy, the energy vectors we use to satisfy our needs and, in general, the configuration of our energy systems. These developments add complexity to our systems as their production and consumption configuration evolve. The concept of sectoral integration is recent and does not yet have a commonly agreed-upon definition nor a consistent measuring approach. We show that network analysis can be used to explore this evolution, allowing quantifying the degree of integration of existing systems. By using a stylized model, we propose a series of global and local measures, focusing on different parts of the energy system and allowing measuring system integration quantitatively. We then illustrate the developed measures by analysing the evolution of two European countries’ energy systems over the recent past (1990–2019).

Dust refers to the amounts of cryptocurrency that are smaller than the fees required to spend them in a transaction. Due to its “economically irrational” nature, dust is often used to achieve some external side effect, rather than exchanging value. In this paper we study this phenomenon by conducting an analysis of dust creation and consumption in the Bitcoin blockchain. We do so by exploiting a new method that allows resource-constrained nodes to retrieve blockchain data by sending authenticated queries to possibly untrusted but more powerful nodes. We validate the method effectiveness experimentally and then analyze the collected data. Results show that a large amount of dust can be traced back to on-chain betting services.

Keeping a physical distance and creating social bubbles are popular measures that have been implemented to prevent infection and slow transmission of COVID-19. Such measures aim to reduce the risk of infection by decreasing the interactions among social networks. This, theoretically, corresponds to the optimal bond percolation (OBP) problem in networks, which is the problem of finding the minimum set of edges whose removal or deactivation from a network would dismantle it into isolated sub-components at most size C. To solve the OBP problem, we proposed a fast-decycling framework composed of three stages: (1) recursively removes influential edges from the 2-core of the network, (2) breaks large trees, and (3) reinserts the unnecessarily removed edges through an explosive percolation process. The proposed approaches perform better than existing OBP algorithms on real-world networks. Our results shed light on the faster design of a more practical social distancing and social bubble policy.

Interactions among objects are usually modelled using graphs. Nevertheless, these relations may change over time and there exist different kind of relations among object that need to be integrated. We introduce a new network model, called temporal dual networks, to deal with interactions that changes over time and to integrate information coming from two different networks. We consider a fundamental problem in graph mining, that is finding densest subgraphs on this new model. We propose an approach based on both network alignment and dynamic programming. Given two temporal graphs, we obtain a dual temporal graph via alignment and then we look for densest subgraphs in the obtained graph. We present a dynamic programming algorithm to solve the problem in polynomial time. Since this algorithm is not applicable even to medium size network, we present a heuristic that is based on (1) constraining the dynamic programming to consider only bounded temporal graphs and (2) a local search procedure. We show that our method is able to return optimal or near optimal solution even for temporal graphs having 10,000 vertices and 10,000 timestamps.

We consider entities interacting over time: individuals meeting, customers buying products, etc., each entity being labeled with some information that may depend on time, and possibly extracted from the interaction nature. Capturing the dynamics as well as the structure of these interactions is of crucial importance for analysis. We are interested here in mining sequences of such interactions. For that purpose, we define core closed patterns in this context and introduce algorithms to enumerate them on a labeled stream graph. We run experiments on two real-world datasets, one representing interactions among students and the other representing citations between authors.

The big break in data collection tools of large-scale networks from biological, social, and technological domains expands the challenge of their visualization and processing. Numerous structural and statistical backbone extraction techniques aim to reduce the network’s size while preserving its gist. Here, we perform an experimental comparison of seven main statistical methods in an air transportation case study. Correlations analysis shows that Marginal Likelihood Filter (MLF), Locally Adaptive Network Sparsification Filter (LANS), and Disparity Filter are biased toward high weighted edges. We compare the extracted backbones using four indicators: the size of the largest component, the number of nodes, edges, and the total weight. Results show that techniques based on a binomial distribution null model (MLF and Noise Corrected Filter) tend to retain many edges. Conversely, Disparity Filter, Polya Urn Filter, LANS Filter, and Global Statistical Significance Filter (GLOSS) are pretty aggressive in filtering edges. The ECM Filter lies between these two behaviors. These results may guide users in selecting appropriate techniques for their applications.

Many complex systems exist in the physical world and therefore can be modeled by networks in which their nodes and edges are embedded in space. However, classical network motifs only use purely topological information and disregard other features. In this paper we introduce a novel and general subgraph abstraction that incorporates spatial information, therefore enriching its characterization power. Moreover, we describe and implement a method to compute and count our spatial subgraphs in any given network. We also provide initial experimental results by using our methodology to produce spatial fingerprints of real road networks, showcasing its discrimination power and how it captures more than just simple topology.

Association Football is probably the world’s most popular sport. Being able to characterise and compare football players is therefore a very important and impactful task. In this work we introduce spatial flow motifs as an extension of previous work on this problem, by incorporating both temporal and spatial information into the network analysis of football data. Our approach considers passing sequences and the role of the player in those sequences, complemented with the physical position of the field where the passes occurred. We provide experimental results of our proposed methodology on real-life event data from the Italian League, showing we can more accurately identify players when compared to using purely topological data.

Heterogeneous player behaviors are commonly observed in games. It is important to quantify and visualize these heterogeneities in order to understand collective behaviors. Our work focuses on developing a Bayesian approach for uncertainty visualization in a model of networked anagram games. In these games, team members collectively form as many words as possible by sharing letters with their neighbors in a network. Heterogeneous player behaviors include great differences in numbers of words formed and the amount of cooperation among networked neighbors. Our Bayesian approach provides meaningful insights for inferring worst, average, and best player performance within behavioral clusters, overcoming previous model shortcomings. These inferences are integrated into a simulation framework to understand the implications of model uncertainty and players’ heterogeneous behaviors.

Integrating complex network theory, link prediction theory, and related research on industrial competition relationship, this paper proposes the theoretically analytical framework of the competitive relationship among Z-Park high-tech enterprises. By constructing a link prediction model, we reveal the internal dynamics that affect the evolution of the competitive network of enterprises, seek the best index reflecting the network formation mechanism, and apply it to the prediction of potential competitive associations.

Time-varying higher-order interactions among more than two units are typically modeled as a temporal higher-order network in the framework of simplicial complex. For the temporal evolution of the higher-order structure of human proximity interactions in five different social settings, previous work found the characteristics of the configuration transitions in a temporal higher-order network before and after triplet interaction events occur. Recently, food science and computing have been attracting attention due to the increasing popularity of recipe sharing services in social media. In this paper, aiming to reveal the characteristics of the temporal evolution of homemade recipes in terms of combinations of ingredients, we propose a method of analyzing the configuration transitions in a temporal higher-order network of ingredients before and after new higher-order links are formed, in the framework of temporal simplicial complex by extending the previous work from a perspective of activity degree of configuration. Using real data of a Japanese recipe sharing service, we empirically demonstrate the effectiveness of the proposed method, and apply it to analyzing the dynamical properties of higher-order networks of ingredients for Japanese homemade recipes.

The between-community beta diversity of fish species—characterized using similarity of species between river basins, shows a non-linear drop with topological distance on river networks. In this work, we investigate the pattern of this drop with network distances and the role of underlying topology. Using the framework of optimal channel networks, the species abundances are evolved under the neutral biodiversity model. We observe that the steady-state species-similarity shows a transition at a critical network distance. At this critical distance, the average degree over the nodes crosses the global average degree of the network. This study sheds light on the role of branching in dendritic networks in ecological community assembly rules.

Wave propagation through nodes and links of a network forms the basis of spectral graph theory. Nevertheless, the sound emitted by nodes within the resonating chamber formed by a network are not well studied. The sound emitted by vibrations of individual nodes reflects the structure of the overall network topology but also the location of the node within the network. In this article a sound recognition neural network is trained to infer centrality measures from the nodes’ wave-forms. In addition to advancing network representation learning, sounds emitted by nodes are plausible in most cases. Auralization of the network topology may open new directions in arts, competing with network visualization.

Temporal networks are networks like physical contact networks whose topology changes over time. Predicting future temporal network is crucial e.g., to forecast and mitigate the spread of epidemics and misinformation on the network. Most existing methods for temporal network prediction are based on machine learning algorithms, at the expense of high computational costs and limited interpretation of the underlying mechanisms that form the networks. This motivates us to develop network-based models to predict the temporal network at the next time step based on the network observed in the past. Firstly, we investigate temporal network properties to motivate our network prediction models and to explain how the performance of these models depends on the temporal networks. We explore the similarity between the network topology (snapshot) at any two time steps with a given time lag/interval. We find that the similarity is relatively high when the time lag is small and decreases as the time lag increases. Inspired by such time-decaying memory of temporal networks and recent advances, we propose two models that predict a link’s future activity (i.e., connected or not), based on the past activities of the link itself or also of neighboring links, respectively. Via seven real-world physical contact networks, we find that our models outperform in both prediction quality and computational complexity, and predict better in networks that have a stronger memory. Beyond, our model also reveals how different types of neighboring links contribute to the prediction of a given link’s future activity, again depending on properties of temporal networks.

This paper aims to understand to what extent the amount of drug (e.g., cocaine) trafficking per country can be explained and predicted using the global shipping network. We propose three distinct network approaches, based on topological centrality metrics, Susceptible-Infected-Susceptible spreading process and a flow optimization model of drug trafficking on the shipping network, respectively. These approaches derive centrality metrics, infection probability, and inflow of drug traffic per country respectively, to estimate the amount of drug trafficking. We use the amount of drug seizure as an approximation of the amount of drug trafficking per country to evaluate our methods. Specifically, we investigate to what extent different methods could predict the ranking of countries in drug seizure (amount). Furthermore, these three approaches are integrated by a linear regression method in which we combine the nodal properties derived by each method to build a comprehensive model for the cocaine seizure data. Our analysis finds that the unweighted eigenvector centrality metric combined with the inflow derived by the flow optimization method best identifies the countries with a large amount of drug seizure (e.g., rank correlation 0.45 with the drug seizure). Extending this regression model with two extra features, the distance of a country from the source of cocaine production and a country’s income group, increases further the prediction quality (e.g., rank correlation 0.79). This final model provides insights into network derived properties and complementary country features that are explanatory for the amount of cocaine seized. The model can also be used to identify countries that have no drug seizure data but are possibly susceptible to cocaine trafficking.