Temporality, a crucial characteristic in the formation of social relationships, was used to quantify the long-term time effects of networks for link prediction models, ignoring the heterogeneity of time effects on different time scales. In this work, we propose a novel approach to link prediction in temporal networks, extending existing methods with a cognitive mechanism that captures the dynamics of the interactions. Our approach computes the weight of the edges and their change over time, similar to memory traces in the human brain, by simulating the process of forgetting and strengthening connections depending on the intensity of interactions. We utilized five ground-truth datasets, which were used to predict social ties, missing events, and potential links. We found: 1) the cognitive mechanism enables more accurate capture of the heterogeneity of the temporal effect, leading to an average precision improvement of 9% compared to baselines with competitive area under curve (AUC); 2) the local structure and synchronous agent behavior contribute differently to different types of datasets; and 3) appropriately increasing the time intervals, which may reduce the negative impact from noise when dividing time windows to calculate the behavioral synchrony of agents, is effective for link prediction tasks.

Finding an optimal subset of nodes or links to disintegrate harmful networks is a fundamental problem in network science, with potential applications to anti-terrorism, epidemic control, and many other fields of study. The challenge of the network disintegration problem is to balance the effectiveness and efficiency of strategies. In this article, we propose a cost-effective targeted enumeration (TE) method for network disintegration. The proposed approach includes two stages: 1) searching for candidate objects and 2) identifying an optimal solution. In the first stage, we use rank aggregation to generate a comprehensive ranking of node importance, upon which we identify a small-scale candidate set of nodes to remove. In the second stage, we use an enumeration method to find an optimal combination among the candidate nodes. Extensive experimental results on synthetic and real-world networks demonstrate that the proposed method achieves a satisfying tradeoff between effectiveness and efficiency. Our adaptable TE approach can effectively address a range of combinatorial optimization challenges with significant potential applications, including personnel recruitment, portfolio management, and pharmaceutical development.

Identifying important nodes for disease spreading is a central topic in network epidemiology. We investigate how well the position of a node, characterized by standard network measures, can predict its epidemiological importance in any graph of a given number of nodes. This is in contrast to other studies that deal with the easier prediction problem of ranking nodes by their epidemic importance in given graphs. As a benchmark for epidemic importance, we calculate the exact expected outbreak size given a node as the source. We study exhaustively all graphs of a given size, so do not restrict ourselves to certain generative models for graphs, nor to graph data sets. Due to the large number of possible nonisomorphic graphs of a fixed size, we are limited to ten-node graphs. We find that combinations of two or more centralities are predictive (R2 scores of 0.91 or higher) even for the most difficult parameter values of the epidemic simulation. Typically, these successful combinations include one normalized spectral centrality (such as PageRank or Katz centrality) and one measure that is sensitive to the number of edges in the graph.

Surveillance plays a crucial role in preventing emerging infectious diseases from becoming epidemic. In circumstances where it is possible to monitor the infection status of certain people, transport hubs, or hospitals, early detection of the disease allows interventions to be implemented before most of the damage can occur, or at least its impact can be mitigated. This paper addresses the question of which nodes we should select in a network of individuals susceptible to some infectious disease in order to minimize the number of casualties. By simulating disease outbreaks on a collection of empirical and synthetic networks we show that the best strategy depends on topological characteristics of the network. For highly modular or spatially embedded networks it is better to place the sentinels on nodes distributed across different regions. However, if the degree heterogeneity is high, then a strategy that targets network hubs is preferred. We further consider the consequences of having an incomplete sample of the network and demonstrate that the value of new information diminishes as more data is collected. Finally we find further marginal improvements using two heuristics informed by known results in graph theory that exploit the fragmented structure of sparse network data.

We investigate methods to vaccinate contact networks-i.e. removing nodes in such a way that disease spreading is hindered as much as possible-with respect to their cost-efficiency. Any real implementation of such protocols would come with costs related both to the vaccination itself, and gathering of information about the network. Disregarding this, we argue, would lead to erroneous evaluation of vaccination protocols. We use the susceptible-infected-recovered model-the generic model for diseases making patients immune upon recovery-as our disease-spreading scenario, and analyze outbreaks on both empirical and model networks. For different relative costs, different protocols dominate. For high vaccination costs and low costs of gathering information, the so-called acquaintance vaccination is the most cost efficient. For other parameter values, protocols designed for query-efficient identification of the network's largest degrees are most efficient.

Many types of social media metadata come in forms of temporal networks, networks where we have information about not only who is in contact with whom but also when contacts happen. In this paper, we review methods to analyze temporal networks developed in the last few years applied to social media data. These methods seek to identify important spreaders and, in more generality, how the temporal and topological structure of interaction affects spreading processes.

One of network epidemiology's central assumptions is that the contact structure over which infectious diseases propagate can be represented as a static network. However, contacts are highly dynamic, changing at many time scales. In this paper, we investigate conceptually simple methods to construct static graphs for network epidemiology from temporal contact data. We evaluate these methods on empirical and synthetic model data. For almost all our cases, the network representation that captures most relevant information is a so-called exponential-threshold network. In these, each contact contributes with a weight decreasing exponentially with time, and there is an edge between a pair of vertices if the weight between them exceeds a threshold. Networks of aggregated contacts over an optimally chosen time window perform almost as good as the exponential-threshold networks. On the other hand, networks of accumulated contacts over the entire sampling time, and networks of concurrent partnerships, perform worse. We discuss these observations in the context of the temporal and topological structure of the data sets.

Sexual contact patterns, both in their temporal and network structure, can influence the spread of sexually transmitted infections (STI). Most previous literature has focused on effects of network topology; few studies have addressed the role of temporal structure. We simulate disease spread using SI and SIR models on an empirical temporal network of sexual contacts in high-end prostitution. We compare these results with several other approaches, including randomization of the data, classic mean-field approaches, and static network simulations. We observe that epidemic dynamics in this contact structure have well-defined, rather high epidemic thresholds. Temporal effects create a broad distribution of outbreak sizes, even if the per-contact transmission probability is taken to its hypothetical maximum of 100%. In general, we conclude that the temporal correlations of our network accelerate outbreaks, especially in the early phase of the epidemics, while the network topology (apart from the contact-rate distribution) slows them down. We find that the temporal correlations of sexual contacts can significantly change simulated outbreaks in a large empirical sexual network. Thus, temporal structures are needed alongside network topology to fully understand the spread of STIs. On a side note, our simulations further suggest that the specific type of commercial sex we investigate is not a reservoir of major importance for HIV.

MOTIVATION: The vastness and complexity of the biochemical networks that have been mapped out by modern genomics calls for decomposition into subnetworks. Such networks can have inherent non-local features that require the global structure to be taken into account in the decomposition procedure. Furthermore, basic questions such as to what extent the network (graph theoretically) can be said to be built by distinct subnetworks are little studied. RESULTS: We present a method to decompose biochemical networks into subnetworks based on the global geometry of the network. This method enables us to analyze the full hierarchical organization of biochemical networks and is applied to 43 organisms from the WIT database. Two types of biochemical networks are considered: metabolic networks and whole-cellular networks (also including for example information processes). Conceptual and quantitative ways of describing the hierarchical ordering are discussed. The general picture of the metabolic networks arising from our study is that of a few core-clusters centred around the most highly connected substances enclosed by other substances in outer shells, and a few other well-defined subnetworks. AVAILABILITY: An implementation of our algorithm and other programs for analyzing the data is available from http://www.tp.umu.se/forskning/networks/meta/ SUPPLEMENTARY INFORMATION: Supplementary material is available at http://www.tp.umu.se/forskning/networks/meta/