Network Science

Natural catastrophes can affect different structures with varying intensities depending on the global and local characteristics of the event. For example, for earthquakes we have global characteristics such as the depth, magnitude, and type (interface or intraslab). Whereas soil conditions, and the hypocentral distance are local characteristics. Here we study the robustness against seismic events of physical-logical interdependent networks used to represent Internet-like systems. To do this we present a novel type of localized attack: Localized Attacks with Probabilistic Failures (LAPF). We use LAPF to model seismic events as Seismic Attacks (SA). We compare the effect of seismic attacks with the effect of localized attacks. To generate these seismic attacks we use real data from earthquakes registered in Chile. We find that seismic attacks can result in catastrophic system failure, and can cause more damage than localized attacks by damaging a smaller fraction of nodes in the physical network. The results also show that catastrophic damage can be prevented by simply adding more interlinks between the logical network and the physical network. We found that seismic attacks that resulted in the loss of more than half of the logical network are related to the removal of logical bridge nodes during the cascading failure, suggesting that the robustness of physical-logical interdependent networks may be improved by identifying and protecting these types of nodes.

An alliance is a formal contingent commitment by two or more states to some future action. Alliances have been widely discussed in the international relations community because hundreds or perhaps thousands of interactions may take place between states in any given year, but few interactions create the impact intended by alliance formation. In this paper, we investigate the historical dynamics of international alliances from a hypernetwork science perspective. Exploring the Formal Alliances dataset from the Correlates of War Project, we focus on three time periods: pre-World War I, pre-World War II, and current day. By using centrality measures such as the notions of s-closeness, s-betweenness, s-eccentricity, and s-local clustering coefficient, we provide a rating benchmark to classify the impact of an alliance.

The availability of large datasets composed of graphs creates an unprecedented need to invent novel tools in statistical learning for graph-valued random variables. To characterize the average of a sample of graphs, one can compute the sample Frechet mean and median graphs. In this paper, we address the following foundational question: does a mean or median graph inherit the structural properties of the graphs in the sample? An important graph property is the edge density; we establish that edge density is an hereditary property, which can be transmitted from a graph sample to its sample Frechet mean or median graphs, irrespective of the method used to estimate the mean or the median. Because of the prominence of the Frechet mean in graph-valued machine learning, this novel theoretical result has some significant practical consequences.

As social interactions are increasingly taking place in the digital environment, online friendship and its effects on various life outcomes from health to happiness attract growing research attention. In most studies, online ties are treated as representing a single type of relationship. However, our online friendship networks are not homogeneous and could include close connections, e.g. a partner, as well as people we have never met in person. In this paper, we investigate the potentially differential effects of online friendship ties on mental health. Using data from a Russian panel study (\(N = 4,400\)), we find that - consistently with previous research - the number of online friends correlates with depression symptoms. However, this is true only for networks that do not exceed Dunbar’s number in size (\(N \le 150\)) and only for core but not peripheral nodes of a friendship network. The findings suggest that online friendship could encode different types of social relationships that should be treated separately while investigating the association between online social integration and life outcomes, in particular well-being or mental health.

The constantly growing size of real-world networks is a great challenge. Therefore, building a compact version of networks allowing their analyses is a must. Backbone extraction techniques are among the leading solutions to reduce network size while preserving its features. Coarse-graining merges similar nodes to reduce the network size, while filter-based methods remove nodes or edges according to a specific statistical property. Since community structure is ubiquitous in real-world networks, preserving it in the backbone extraction process is of prime interest. To this end, we propose a filter-based method. The so-called “modularity vitality backbone” removes nodes with the lower contribution to the network’s modularity. Experimental results show that the proposed strategy outperforms the “overlapping nodes ego backbone” and the “overlapping nodes and hub backbone.” These two backbone extraction processes recently introduced have proved their efficacy to preserve better the information of the original network than the popular disparity filter.

As the world’s population continues to expand, maritime transport is critical to ensure economic growth. To improve security and safety of maritime transportation, the Automatic Identification System (AIS) collects real-time data about vessels and their positions. While a large portion of the AIS data is provided via an automatic tracking system, some key fields, such as destination and draught, are entered manually by the ship navigator and are thus prone to errors. To support decision making in maritime industries, in this paper we propose a data-driven vessel destination prediction algorithm based on heterogeneous graph and machine learning models. We design the task as a multi-class classification problem, where the destination port is the category to be predicted given the vessel and origin information. Then, we use a link prediction model in a weighted heterogeneous graph to predict the vessel destination. Experimental comparison against baseline methods, such as logistic regression and k-nearest neighbors, showed that our model provides a robust performance, outperforming the baseline algorithms by 9% and 33% in terms of accuracy and F1-score, respectively. Thus, heterogeneous graph models provide a powerful alternative to predict port destination, and could support enhancing AIS data quality and better decision making in maritime transportation industries.

In the past decades, complex networks have proved to be an exceedingly powerful and efficacious tool for describing a wide range of systems in nature and society. Thereafter, random search processes, as an effective and informative way of exploring these networks, have attracted considerable attention towards them. In this work, we study the problem of partial cover time in a dual-target search when performing a random walk on a (1,2)-flower network. For the first time, we derive an exact expression for the partial cover time of a random searcher on such a network to hunt both target nodes of interest. The introduced formula for calculating this quantity outranks previous work in the sense that it can be conveniently applied to general types of networks. Utilizing this expression can introduce a pivotal change for efficiently solving the problem of partial cover time in its wide range of applicable fields.

We discuss a unified framework for the statistical analysis of streaming data obtained by networks with a known neighborhood structure. In particular, we deal with autoregressive models that make explicit the dependence of current observations to their past values and the values of their respective neighborhoods. We consider the case of both continuous and count responses measured over time for each node of a known network. We discuss least squares and quasi maximum likelihood inference. Both methods provide estimators with good properties. In particular, we show that consistent and asymptotically normal estimators of the model parameters, under this high-dimensional data generating process, are obtained after optimizing a criterion function. The methodology is illustrated by applying it to wind speed observed over different weather stations of England and Wales.

Scale-free networks have been described as robust to random failures but vulnerable to targeted attacks. We show that their degree sequences admit realizations that are, in fact, provably robust against any vertex removal strategy. We propose an algorithm that constructs such realizations almost surely, requiring only linear time and space. Our experiments confirm the robustness of the networks generated by this algorithm against adaptive and non-adaptive vertex removal strategies.

Transcriptional regulatory networks are responsible for controlling gene expression. These networks are composed of many interactions between transcription factors and their target genes. Carrying a combinatorial nature that encompasses several regulatory processes, they allow an organism to respond to disturbances that may occur in the surrounding environment. In this work, we study transcriptional regulatory networks of closely related yeast species with the aim of revealing which functions or processes are encoded in the regulatory network topology. The first phase of this work consists of the detection of modules followed by their functional characterization. Here, we unveil the functionality of the species by capturing it in functional modules. In the second phase, we move towards a cross-species analysis where we compare the functional modules of the different species to settle the similarities between them. Lastly, we use a multilayer network approach to combine the genetic information of different species. We seek to identify the functional elements conserved across the different organisms by applying a detection of modules in the multilayer network.

Information spreading on social networks is one of the most important topics in network science and has long been actively studied. However, most studies only focus on the spread of a single piece of information on random networks, even though information spreading in the real world is much more complicated, involving a complex topology structure and interactions between multiple information. Therefore, in this paper, we model the competitive information spreading on modular networks and investigate how the community structure affects competitive information spreading in two spreading scenarios: sequential and simultaneous. In the sequential spreading scenario, we find that the community structure has little effect on the final prevalence but affects the spreading process (time evolution of the prevalence). In contrast, in the simultaneous spreading scenario, we find that community structure has a strong effect on not only the spreading process but also the final prevalence. Specifically, two competing pieces of information cannot coexist and one drives out the other on a non-modular network, whereas they can coexist in different communities on a modular network. Our results suggest that the effect of community structure cannot be ignored in the analysis of competitive spreading (especially, simultaneous spreading) of multiple information.

Many problems such as node classification and link prediction in network data can be solved using graph embeddings. However, it is difficult to use graphs to capture non-binary relations such as communities of nodes. These kinds of complex relations are expressed more naturally as hypergraphs. While hypergraphs are a generalization of graphs, state-of-the-art graph embedding techniques are not adequate for solving prediction and classification tasks on large hypergraphs accurately in reasonable time. In this paper, we introduce HyperNetVec, a novel hierarchical framework for scalable unsupervised hypergraph embedding. HyperNetVec exploits shared-memory parallelism and is capable of generating high quality embeddings for real-world hypergraphs with millions of nodes and hyperedges in only a couple of minutes while existing hypergraph systems either fail for such large hypergraphs or may take days to produce the embeddings.