Metrics for network comparison using egonet feature distributions.

Identifying networks with similar characteristics in a given ensemble, or detecting pattern discontinuities in a temporal sequence of networks, are two examples of tasks that require an effective metric capable of quantifying network (dis)similarity. Here we propose a method based on a global portrait of graph properties built by processing local nodes features. More precisely, a set of dissimilarity measures is defined by elaborating the distributions, over the network, of a few egonet features, namely the degree, the clustering coefficient, and the egonet persistence. The method, which does not require the alignment of the two networks being compared, exploits the statistics of the three features to define one- or multi-dimensional distribution functions, which are then compared to define a distance between the networks. The effectiveness of the method is evaluated using a standard classification test, i.e., recognizing the graphs originating from the same synthetic model. Overall, the proposed distances have performances comparable to the best state-of-the-art techniques (graphlet-based methods) with similar computational requirements. Given its simplicity and flexibility, the method is proposed as a viable approach for network comparison tasks.

A Graphlet-Based Topological Characterization of the Resting-State Network in Healthy People.

In this paper, we propose a graphlet-based topological algorithm for the investigation of the brain network at resting state (RS). To this aim, we model the brain as a graph, where (labeled) nodes correspond to specific cerebral areas and links are weighted connections determined by the intensity of the functional magnetic resonance imaging (fMRI). Then, we select a number of working graphlets, namely, connected and non-isomorphic induced subgraphs. We compute, for each labeled node, its Graphlet Degree Vector (GDV), which allows us to associate a GDV matrix to each one of the 133 subjects of the considered sample, reporting how many times each node of the atlas "touches" the independent orbits defined by the graphlet set. We focus on the 56 independent columns (i.e., non-redundant orbits) of the GDV matrices. By aggregating their count all over the 133 subjects and then by sorting each column independently, we obtain a sorted node table, whose top-level entries highlight the nodes (i.e., brain regions) most frequently touching each of the 56 independent graphlet orbits. Then, by pairwise comparing the columns of the sorted node table in the top-k entries for various values of k, we identify sets of nodes that are consistently involved with high frequency in the 56 independent graphlet orbits all over the 133 subjects. It turns out that these sets consist of labeled nodes directly belonging to the default mode network (DMN) or strongly interacting with it at the RS, indicating that graphlet analysis provides a viable tool for the topological characterization of such brain regions. We finally provide a validation of the graphlet approach by testing its power in catching network differences. To this aim, we encode in a Graphlet Correlation Matrix (GCM) the network information associated with each subject then construct a subject-to-subject Graphlet Correlation Distance (GCD) matrix based on the Euclidean distances between all possible pairs of GCM. The analysis of the clusters induced by the GCD matrix shows a clear separation of the subjects in two groups, whose relationship with the subject characteristics is investigated.

Topology comparison of Twitter diffusion networks effectively reveals misleading information.

In recent years, malicious information had an explosive growth in social media, with serious social and political backlashes. Recent important studies, featuring large-scale analyses, have produced deeper knowledge about this phenomenon, showing that misleading information spreads faster, deeper and more broadly than factual information on social media, where echo chambers, algorithmic and human biases play an important role in diffusion networks. Following these directions, we explore the possibility of classifying news articles circulating on social media based exclusively on a topological analysis of their diffusion networks. To this aim we collected a large dataset of diffusion networks on Twitter pertaining to news articles published on two distinct classes of sources, namely outlets that convey mainstream, reliable and objective information and those that fabricate and disseminate various kinds of misleading articles, including false news intended to harm, satire intended to make people laugh, click-bait news that may be entirely factual or rumors that are unproven. We carried out an extensive comparison of these networks using several alignment-free approaches including basic network properties, centrality measures distributions, and network distances. We accordingly evaluated to what extent these techniques allow to discriminate between the networks associated to the aforementioned news domains. Our results highlight that the communities of users spreading mainstream news, compared to those sharing misleading news, tend to shape diffusion networks with subtle yet systematic differences which might be effectively employed to identify misleading and harmful information.

Comparing methods for comparing networks.

With the impressive growth of available data and the flexibility of network modelling, the problem of devising effective quantitative methods for the comparison of networks arises. Plenty of such methods have been designed to accomplish this task: most of them deal with undirected and unweighted networks only, but a few are capable of handling directed and/or weighted networks too, thus properly exploiting richer information. In this work, we contribute to the effort of comparing the different methods for comparing networks and providing a guide for the selection of an appropriate one. First, we review and classify a collection of network comparison methods, highlighting the criteria they are based on and their advantages and drawbacks. The set includes methods requiring known node-correspondence, such as DeltaCon and Cut Distance, as well as methods not requiring a priori known node-correspondence, such as alignment-based, graphlet-based, and spectral methods, and the recently proposed Portrait Divergence and NetLSD. We test the above methods on synthetic networks and we assess their usability and the meaningfulness of the results they provide. Finally, we apply the methods to two real-world datasets, the European Air Transportation Network and the FAO Trade Network, in order to discuss the results that can be drawn from this type of analysis.

Direct reciprocity and model-predictive rationality explain network reciprocity over social ties.

Since M. A. Nowak & R. May's (1992) influential paper, limiting each agent's interactions to a few neighbors in a network of contacts has been proposed as the simplest mechanism to support the evolution of cooperation in biological and socio-economic systems. The network allows cooperative agents to self-assort into clusters, within which they reciprocate cooperation. This (induced) network reciprocity has been observed in several theoreticalmodels and shown to predict the fixation of cooperation under a simple rule: the benefit produced by an act of cooperation must outweigh the cost of cooperating with all neighbors. However, the experimental evidence among humans is controversial: though the rule seems to be confirmed, the underlying modeling assumptions are not. Specifically, models assume that agents update their strategies by imitating better performing neighbors, even though imitation lacks rationality when interactions are far from all-to-all. Indeed, imitation did not emerge in experiments. What did emerge is that humans are conditioned by their own mood and that, when in a cooperative mood, they reciprocate cooperation. To help resolve the controversy, we design a model in which we rationally confront the two main behaviors emerging from experiments-reciprocal cooperation and unconditional defection-in a networked prisoner's dilemma. Rationality is introduced by means of a predictive rule for strategy update and is bounded by the assumed model society. We show that both reciprocity and a multi-step predictive horizon are necessary to stabilize cooperation, and sufficient for its fixation, provided the game benefit-to-cost ratio is larger than a measure of network connectivity. We hence rediscover the rule of network reciprocity, underpinned however by a different evolutionary mechanism.

Complexity, centralization, and fragility in economic networks.

Trade networks, across which countries distribute their products, are crucial components of the globalized world economy. Their structure affects the mechanism of propagation of shocks from country to country, as observed in a very sharp way in the past decade, characterized by economic uncertainty in many parts of the world. Such trade structures are strongly heterogeneous across products, given the different features of the countries which buy and sell goods. By using a diversified pool of indicators from network science and product complexity theory, we quantitatively demonstrate that, overall, products with higher complexity-i.e., with larger technological content and/or number of components-are traded through more centralized networks-i.e., with a smaller number of countries concentrating most of the export flow. Since centralized networks are known to be more vulnerable, we argue that the current composition of production and trading is associated to high fragility at the level of the most complex-thus strategic-products.

Link Prediction in Criminal Networks: A Tool for Criminal Intelligence Analysis.

The problem of link prediction has recently received increasing attention from scholars in network science. In social network analysis, one of its aims is to recover missing links, namely connections among actors which are likely to exist but have not been reported because data are incomplete or subject to various types of uncertainty. In the field of criminal investigations, problems of incomplete information are encountered almost by definition, given the obvious anti-detection strategies set up by criminals and the limited investigative resources. In this paper, we work on a specific dataset obtained from a real investigation, and we propose a strategy to identify missing links in a criminal network on the basis of the topological analysis of the links classified as marginal, i.e. removed during the investigation procedure. The main assumption is that missing links should have opposite features with respect to marginal ones. Measures of node similarity turn out to provide the best characterization in this sense. The inspection of the judicial source documents confirms that the predicted links, in most instances, do relate actors with large likelihood of co-participation in illicit activities.

Discovering Preferential Patterns in Sectoral Trade Networks.

We analyze the patterns of import/export bilateral relations, with the aim of assessing the relevance and shape of "preferentiality" in countries' trade decisions. Preferentiality here is defined as the tendency to concentrate trade on one or few partners. With this purpose, we adopt a systemic approach through the use of the tools of complex network analysis. In particular, we apply a pattern detection approach based on community and pseudocommunity analysis, in order to highlight the groups of countries within which most of members' trade occur. The method is applied to two intra-industry trade networks consisting of 221 countries, relative to the low-tech "Textiles and Textile Articles" and the high-tech "Electronics" sectors for the year 2006, to look at the structure of world trade before the start of the international financial crisis. It turns out that the two networks display some similarities and some differences in preferential trade patterns: they both include few significant communities that define narrow sets of countries trading with each other as preferential destinations markets or supply sources, and they are characterized by the presence of similar hierarchical structures, led by the largest economies. But there are also distinctive features due to the characteristics of the industries examined, in which the organization of production and the destination markets are different. Overall, the extent of preferentiality and partner selection at the sector level confirm the relevance of international trade costs still today, inducing countries to seek the highest efficiency in their trade patterns.

Connectivity interplays with age in shaping contagion over networks with vital dynamics.

The effects of network topology on the emergence and persistence of infectious diseases have been broadly explored in recent years. However, the influence of the vital dynamics of the hosts (i.e., birth-death processes) on the network structure, and their effects on the pattern of epidemics, have received less attention in the scientific community. Here, we study Susceptible-Infected-Recovered(-Susceptible) [SIR(S)] contact processes in standard networks (of Erdös-Rényi and Barabási-Albert type) that are subject to host demography. Accounting for the vital dynamics of hosts is far from trivial, and it causes the scale-free networks to lose their characteristic fat-tailed degree distribution. We introduce a broad class of models that integrate the birth and death of individuals (nodes) with the simplest mechanisms of infection and recovery, thus generating age-degree structured networks of hosts that interact in a complex manner. In our models, the epidemiological state of each individual may depend both on the number of contacts (which changes through time because of the birth-death process) and on its age, paving the way for a possible age-dependent description of contagion and recovery processes. We study how the proportion of infected individuals scales with the number of contacts among them. Rather unexpectedly, we discover that the result of highly connected individuals at the highest risk of infection is not as general as commonly believed. In infections that confer permanent immunity to individuals of vital populations (SIR processes), the nodes that are most likely to be infected are those with intermediate degrees. Our age-degree structured models allow such findings to be deeply analyzed and interpreted, and they may aid in the development of effective prevention policies.

Community analysis in directed networks: in-, out-, and pseudocommunities.

When analyzing important classes of complex interconnected systems, link directionality can hardly be neglected if a precise and effective picture of the structure and function of the system is needed. If community analysis is performed, the notion of "community" itself is called into question, since the property of having a comparatively looser external connectivity could refer to the inbound or outbound links only or to both categories. In this paper, we introduce the notions of in-, out-, and in-/out-community in order to correctly classify the directedness of the interaction of a subnetwork with the rest of the system. Furthermore, we extend the scope of community analysis by introducing the notions of in-, out-, and in-/out-pseudocommunity. They are subnetworks having strong internal connectivity but also important interactions with the rest of the system, the latter taking place by means of a minority of its nodes only. The various types of (pseudo-)communities are qualified and distinguished by a suitable set of indicators and, on a given network, they can be discovered by using a "local" searching algorithm. The application to a broad set of benchmark networks and real-world examples proves that the proposed approach is able to effectively disclose the different types of structures above defined and to usefully classify the directionality of their interactions with the rest of the system.

Profiling core-periphery network structure by random walkers.

Disclosing the main features of the structure of a network is crucial to understand a number of static and dynamic properties, such as robustness to failures, spreading dynamics, or collective behaviours. Among the possible characterizations, the core-periphery paradigm models the network as the union of a dense core with a sparsely connected periphery, highlighting the role of each node on the basis of its topological position. Here we show that the core-periphery structure can effectively be profiled by elaborating the behaviour of a random walker. A curve--the core-periphery profile--and a numerical indicator are derived, providing a global topological portrait. Simultaneously, a coreness value is attributed to each node, qualifying its position and role. The application to social, technological, economical, and biological networks reveals the power of this technique in disclosing the overall network structure and the peculiar role of some specific nodes.

Existence and significance of communities in the World Trade Web.

The World Trade Web (WTW), which models the international transactions among countries, is a fundamental tool for studying the economics of trade flows, their evolution over time, and their implications for a number of phenomena, including the propagation of economic shocks among countries. In this respect, the possible existence of communities is a key point, because it would imply that countries are organized in groups of preferential partners. In this paper, we use four approaches to analyze communities in the WTW between 1962 and 2008, based, respectively, on modularity optimization, cluster analysis, stability functions, and persistence probabilities. Overall, the four methods agree in finding no evidence of significant partitions. A few weak communities emerge from the analysis, but they do not represent secluded groups of countries, as intercommunity linkages are also strong, supporting the view of a truly globalized trading system.

Finding and testing network communities by lumped Markov chains.

Identifying communities (or clusters), namely groups of nodes with comparatively strong internal connectivity, is a fundamental task for deeply understanding the structure and function of a network. Yet, there is a lack of formal criteria for defining communities and for testing their significance. We propose a sharp definition that is based on a quality threshold. By means of a lumped Markov chain model of a random walker, a quality measure called "persistence probability" is associated to a cluster, which is then defined as an "α-community" if such a probability is not smaller than α. Consistently, a partition composed of α-communities is an "α-partition." These definitions turn out to be very effective for finding and testing communities. If a set of candidate partitions is available, setting the desired α-level allows one to immediately select the α-partition with the finest decomposition. Simultaneously, the persistence probabilities quantify the quality of each single community. Given its ability in individually assessing each single cluster, this approach can also disclose single well-defined communities even in networks that overall do not possess a definite clusterized structure.

Synchrony in tritrophic food chain metacommunities.

The synchronous behaviour of interacting communities is studied in this paper. Each community is described by a tritrophic food chain model, and the communities interact through a network with arbitrary topology, composed of patches and migration corridors. The analysis of the local synchronization properties (via the master stability function approach) shows that, if only one species can migrate, the dispersal of the consumer (i.e., the intermediate trophic level) is the most effective mechanism for promoting synchronization. When analysing the effects of the variations of demographic parameters, it is found that factors that stabilize the single community also tend to favour synchronization. Global synchronization is finally analysed by means of the connection graph method, yielding a lower bound on the value of the dispersion rate that guarantees the synchronization of the metacommunity for a given network topology.

Inefficient epidemic spreading in scale-free networks.

Highly heterogeneous degree distributions yield efficient spreading of simple epidemics through networks, but can be inefficient with more complex epidemiological processes. We study diseases with nonlinear force of infection whose prevalences can abruptly collapse to zero while decreasing the transmission parameters. We find that scale-free networks can be unable to support diseases that, on the contrary, are able to persist at high endemic levels in homogeneous networks with the same average degree.

On parameter estimation of chaotic systems via symbolic time-series analysis.

Symbolic time-series analysis is used for estimating the parameters of chaotic systems. It is assumed that a "target model" (i.e., a discrete- or continuous-time description of the data-generating mechanism) is available, but with unknown parameters. A time series, i.e., a noisy, finite sequence of a measured (output) variable, is given. The proposed method first prescribes to symbolize the time series, i.e., to transform it into a sequence of symbols, from which the statistics of symbols are readily derived. Then, a symbolic model (in the form of a Markov chain) is derived from the data. It allows one to predict, in a probabilistic fashion, the time evolution of the symbol sequence. The unknown parameters are derived by matching either the statistics of symbols, or the symbolic prediction derived from data, with those generated by the (parametrized) target model. Three examples of application (the Henon map, a population model, and the Duffing system) prove that satisfactory results can be obtained even with short time series.

On the control of chaotic systems via symbolic time series analysis.

Symbolic analysis of time series is extended to systems with inputs, in order to obtain input/output symbolic models to be used for control policy design. For that, the notion of symbolic word is broadened to possibly include past input values. Then, a model is derived in the form of a controlled Markov chain, i.e., transition probabilities are conditioned on the control value. The quality of alternative models with different word length and alphabet size is assessed by means of an indicator based on Shannon entropy. A control problem is formulated, with the goal of confining the system output in a smaller domain with respect to that of the uncontrolled case. Solving this problem (by means of a suitable numerical method) yields the relevant control policy, as well as an estimate of the probability distribution of the output of the controlled system. Three examples of application (based on the analysis of time series synthetically generated by the logistic map, the Lorenz system, and an epidemiological model) are presented and used to discuss the features and limitations of the method.