Showing 1–50 of 61 results for author: Saramäki, J

Multiplexity is temporal: effects of social times on network structure

Authors: Javier Ureña-Carrion, Sara Heydari, Talayeh Aledavood, Jari Saramäki, Mikko Kivelä

Abstract: Large-scale social networks constructed using contact metadata have been invaluable tools for understanding and testing social theories of society-wide social structures. However, multiplex relationships explaining different social contexts have been out of reach of this methodology, limiting our ability to understand this crucial aspect of social systems. We propose a method that infers latent so… ▽ More Large-scale social networks constructed using contact metadata have been invaluable tools for understanding and testing social theories of society-wide social structures. However, multiplex relationships explaining different social contexts have been out of reach of this methodology, limiting our ability to understand this crucial aspect of social systems. We propose a method that infers latent social times from the weekly activity of large-scale contact metadata, and reconstruct multilayer networks where layers correspond to social times. We then analyze the temporal multiplexity of ties in a society-wide communication network of millions of individuals. This allows us to test the propositions of Feld's social focus theory across a society-wide network: We show that ties favour their own social times regardless of contact intensity, suggesting they reflect underlying social foci. We present a result on strength of monoplex ties, which indicates that monoplex ties are bridging and even more important for global network connectivity than the weak, low-contact ties. Finally, we show that social times are transitive, so that when egos use a social time for a small subset of alters, the alters use the social time among themselves as well. Our framework opens up a way to analyse large-scale communication as multiplex networks and uncovers society-level patterns of multiplex connectivity. △ Less

Submitted 8 July, 2024; originally announced July 2024.

Distinguishing subsampled power laws from other heavy-tailed distributions

Authors: Silja Sormunen, Lasse Leskelä, Jari Saramäki

Abstract: Distinguishing power-law distributions from other heavy-tailed distributions is challenging, and this task is often further complicated by subsampling effects. In this work, we evaluate the performance of two commonly used methods for detecting power-law distributions - the maximum likelihood method of Clauset et al. and the extreme value method of Voitalov et al. - in distinguishing subsampled po… ▽ More Distinguishing power-law distributions from other heavy-tailed distributions is challenging, and this task is often further complicated by subsampling effects. In this work, we evaluate the performance of two commonly used methods for detecting power-law distributions - the maximum likelihood method of Clauset et al. and the extreme value method of Voitalov et al. - in distinguishing subsampled power laws from two other heavy-tailed distributions, the lognormal and the stretched exponential distributions. We focus on a random subsampling method commonly applied in network science and biological sciences. In this subsampling scheme, we are ultimately interested in the frequency distribution of elements with a certain number of constituent parts, and each part is selected to the subsample with an equal probability. We investigate how well the results obtained from subsamples generalize to the original distribution. Our results show that the power-law exponent of the original distribution can be estimated fairly accurately from subsamples, but classifying the distribution correctly is more challenging. The maximum likelihood method falsely rejects the power-law hypothesis for a large fraction of subsamples from power-law distributions. While the extreme value method correctly recognizes subsampled power-law distributions with all tested subsampling depths, its capacity to distinguish power laws from the heavy-tailed alternatives is limited. However, these false positives tend to result not from the subsampling itself but from the estimators' inability to classify the original sample correctly. In fact, we show that the extreme value method can sometimes be expected to perform better on subsamples than on the original samples from the lognormal and the stretched exponential distributions, while the contrary is true for the main tests included in the maximum likelihood method. △ Less

Submitted 15 April, 2024; originally announced April 2024.

Journal ref: Physical Review E 109, 054308 (2024)

Disentangling degree and tie strength heterogeneity in egocentric social networks

Authors: Sara Heydari, Gerardo Iñiguez, János Kertész, Jari Saramäki

Abstract: The structure of personal networks reflects how we organise and maintain social relationships. The distribution of tie strengths in personal networks is heterogeneous, with a few close, emotionally intense relationships and a larger number of weaker ties. Recent results indicate this feature is universal across communication channels. Within this general pattern, there is a substantial and persist… ▽ More The structure of personal networks reflects how we organise and maintain social relationships. The distribution of tie strengths in personal networks is heterogeneous, with a few close, emotionally intense relationships and a larger number of weaker ties. Recent results indicate this feature is universal across communication channels. Within this general pattern, there is a substantial and persistent inter-individual variation that is also similarly distributed among channels. The reason for the observed universality is yet unclear -- one possibility is that people's traits determine their personal network features on any channel. To address this hypothesis, we need to compare an individual's personal networks across channels, which is a non-trivial task: while we are interested in measuring the differences in tie strength heterogeneity, personal network size is also expected to vary a lot across channels. Therefore, for any measure that compares personal networks, one needs to understand the sensitivity with respect to network size. Here, we study different measures of personal network similarity and show that a recently introduced alter-preferentiality parameter and the Gini coefficient are equally suitable measures for tie strength heterogeneity, as they are fairly insensitive to differences in network size. With these measures, we show that the earlier observed individual-level persistence of personal network structure cannot be attributed to network size stability alone, but that the tie strength heterogeneity is persistent too. We also demonstrate the effectiveness of the two measures on multichannel data, where tie strength heterogeneity in personal networks is seen to moderately correlate for the same users across two communication channels (calls and text messages). △ Less

Submitted 28 March, 2024; originally announced March 2024.

Comments: 25 pages, 10 figures

Strength and weakness of disease-induced herd immunity in networks

Authors: Takayuki Hiraoka, Zahra Ghadiri, Abbas K. Rizi, Mikko Kivelä, Jari Saramäki

Abstract: When a fraction of a population becomes immune to an infectious disease, the population-wide infection risk decreases nonlinearly due to collective protection known as herd immunity. Studies based on mean-field models suggest that natural infection in a heterogeneous population may induce herd immunity more efficiently than homogeneous immunization. Here, we use network epidemic models to show tha… ▽ More When a fraction of a population becomes immune to an infectious disease, the population-wide infection risk decreases nonlinearly due to collective protection known as herd immunity. Studies based on mean-field models suggest that natural infection in a heterogeneous population may induce herd immunity more efficiently than homogeneous immunization. Here, we use network epidemic models to show that the opposite can also be the case. We identify two competing mechanisms driving disease-induced herd immunity in networks: the high density of immunity among socially active individuals enhances the herd immunity effect, while the topological localization of immune individuals weakens it. The effect of localization is stronger in networks embedded in low-dimensional space, which can make disease-induced immunity less effective than random immunization. Our results highlight the role of networks in shaping herd immunity and call for careful examination of model predictions that inform public health policies. △ Less

Submitted 3 July, 2024; v1 submitted 10 July, 2023; originally announced July 2023.

Comments: Main text: 11 pages, 4 figures. Supplementary Materials: 8 pages, 2 figures

Universal patterns in egocentric communication networks

Authors: Gerardo Iñiguez, Sara Heydari, János Kertész, Jari Saramäki

Abstract: Tie strengths in social networks are heterogeneous, with strong and weak ties playing different roles at both the network and the individual level. Egocentric networks, networks of relationships around a focal individual, exhibit a small number of strong ties and a larger number of weaker ties, a pattern that is evident in electronic communication records, such as mobile phone calls. Mobile phone… ▽ More Tie strengths in social networks are heterogeneous, with strong and weak ties playing different roles at both the network and the individual level. Egocentric networks, networks of relationships around a focal individual, exhibit a small number of strong ties and a larger number of weaker ties, a pattern that is evident in electronic communication records, such as mobile phone calls. Mobile phone data has also revealed persistent individual differences within this pattern. However, the generality and the driving mechanisms of this tie strength heterogeneity remain unclear. Here, we study tie strengths in egocentric networks across multiple datasets containing records of interactions between millions of people over time periods ranging from months to years. Our findings reveal a remarkable universality in the distribution of tie strengths and their individual-level variation across different modes of communication, even in channels that may not reflect offline social relationships. With the help of an analytically tractable model of egocentric network evolution, we show that the observed universality can be attributed to the competition between cumulative advantage and random choice, two general mechanisms of tie reinforcement whose balance determines the amount of heterogeneity in tie strengths. Our results provide new insights into the driving mechanisms of tie strength heterogeneity in social networks and have implications for the understanding of social network structure and individual behavior. △ Less

Submitted 27 February, 2023; originally announced February 2023.

Comments: 13 pages, 3 figures. SI: 21 pages, 10 figures

Journal ref: Iñiguez, G., Heydari, S., Kertész, J., Saramäki, J. Universal patterns in egocentric communication networks. Nature Communications 14, 5217 (2023)

Herd Immunity and Epidemic Size in Networks with Vaccination Homophily

Authors: Takayuki Hiraoka, Abbas K. Rizi, Mikko Kivelä, Jari Saramäki

Abstract: We study how the herd immunity threshold and the expected epidemic size depend on homophily with respect to vaccine adoption. We find that the presence of homophily considerably increases the critical vaccine coverage needed for herd immunity and that strong homophily can push the threshold entirely out of reach. The epidemic size monotonically increases as a function of homophily strength for a p… ▽ More We study how the herd immunity threshold and the expected epidemic size depend on homophily with respect to vaccine adoption. We find that the presence of homophily considerably increases the critical vaccine coverage needed for herd immunity and that strong homophily can push the threshold entirely out of reach. The epidemic size monotonically increases as a function of homophily strength for a perfect vaccine, while it is maximized at a nontrivial level of homophily when the vaccine efficacy is limited. Our results highlight the importance of vaccination homophily in epidemic modeling. △ Less

Submitted 28 March, 2022; v1 submitted 14 December, 2021; originally announced December 2021.

Comments: 12 pages, 9 figures

Mobility signatures: a tool for characterizing cities using intercity mobility flows

Authors: Maryam Kiashemshaki, Zhiren Huang, Jari Saramäki

Abstract: Understanding the patterns of human mobility between cities has various applications from transport engineering to spatial modeling of the spreading of contagious diseases. We adopt a city-centric, data-driven perspective to quantify such patterns and introduce the mobility signature as a tool for understanding how a city (or a region) is embedded in the wider mobility network. We demonstrate the… ▽ More Understanding the patterns of human mobility between cities has various applications from transport engineering to spatial modeling of the spreading of contagious diseases. We adopt a city-centric, data-driven perspective to quantify such patterns and introduce the mobility signature as a tool for understanding how a city (or a region) is embedded in the wider mobility network. We demonstrate the potential of the mobility signature approach through two applications that build on mobile-phone-based data from Finland. First, we use mobility signatures to show that the well-known radiation model is more accurate for mobility flows associated with larger cities, while the traditional gravity model appears a better fit for less populated areas. Second, we illustrate how the SARS-CoV-2 pandemic disrupted the mobility patterns in Finland in the spring of 2020. These two cases demonstrate the ability of the mobility signatures to quickly capture features of mobility flows that are harder to extract using more traditional methods. △ Less

Submitted 3 December, 2021; originally announced December 2021.

Comments: 13 pages, 5 figures

Journal ref: Front. Big Data (2022) 5:822889

A map of approaches to temporal networks

Authors: Petter Holme, Jari Saramäki

Abstract: The study of temporal networks is motivated by the simple and important observation that just as network structure can affect dynamics, so can structure in time. Just as network topology can teach us about the system in question, so can its temporal characteristics. In many cases, leaving out either one of these components would lead to an incomplete understanding of the system or poor predictions… ▽ More The study of temporal networks is motivated by the simple and important observation that just as network structure can affect dynamics, so can structure in time. Just as network topology can teach us about the system in question, so can its temporal characteristics. In many cases, leaving out either one of these components would lead to an incomplete understanding of the system or poor predictions. We argue that including time into network modeling inevitably leads researchers away from the trodden paths of network science. Temporal network theory requires something different -- new methods, new concepts, new questions -- compared to static networks. In this introductory chapter, we overview the ideas that the field of temporal networks has brought forward in the last decade. We also place the contributions to the current volume on this map of temporal-network approaches. △ Less

Submitted 25 March, 2021; originally announced March 2021.

Comments: Introductory chapter to the book: Holme, Saramäki, Temporal Network Theory (Springer, Cham, 2019)

Journal ref: In: Holme, Saramäki, Temporal Network Theory (Springer, Cham, 2019), pp. 1-24

Temporal networks as a modeling framework

Authors: Petter Holme, Jari Saramäki

Abstract: To understand large, connected systems, we cannot only zoom into the details. We also need to see the large-scale features from afar. One way to take a step back and get the whole picture is to model the systems as a network. However, many systems are not static, but consisting of contacts that are off and on as time progresses. This Chapter introduces the mathematical and computational modeling o… ▽ More To understand large, connected systems, we cannot only zoom into the details. We also need to see the large-scale features from afar. One way to take a step back and get the whole picture is to model the systems as a network. However, many systems are not static, but consisting of contacts that are off and on as time progresses. This Chapter introduces the mathematical and computational modeling of such systems and thus an introduction to the rest of the book. We will cover some of the earlier developments that form the foundation for the more specialized topics of the other Chapters. △ Less

Submitted 24 March, 2021; originally announced March 2021.

Comments: Introductory chapter to Holme, Saramäki, eds., Temporal Networks (Springer, Berlin, 2013)

Journal ref: In: Holme, Saramäki, eds., Temporal Networks (Springer, Berlin, 2013), pp. 1-14

A Non-negative Matrix Factorization Based Method for Quantifying Rhythms of Activity and Sleep and Chronotypes Using Mobile Phone Data

Authors: Talayeh Aledavood, Ilkka Kivimäki, Sune Lehmann, Jari Saramäki

Abstract: Human activities follow daily, weekly, and seasonal rhythms. The emergence of these rhythms is related to physiology and natural cycles as well as social constructs. The human body and biological functions undergo near 24-hour rhythms (circadian rhythms). The frequency of these rhythms is more or less similar across people, but its phase is different. In the chronobiology literature, based on the… ▽ More Human activities follow daily, weekly, and seasonal rhythms. The emergence of these rhythms is related to physiology and natural cycles as well as social constructs. The human body and biological functions undergo near 24-hour rhythms (circadian rhythms). The frequency of these rhythms is more or less similar across people, but its phase is different. In the chronobiology literature, based on the propensity to sleep at different hours of the day, people are categorized into morning-type, evening-type, and intermediate-type groups called \textit{chronotypes}. This typology is typically based on carefully designed questionnaires or manually crafted features drawing on data on timings of people's activity. Here we develop a fully data-driven (unsupervised) method to decompose individual temporal activity patterns into components. This has the advantage of not including any predetermined assumptions about sleep and activity hours, but the results are fully context-dependent and determined by the most prominent features of the activity data. Using a year-long dataset from mobile phone screen usage logs of 400 people, we find four emergent temporal components: morning activity, night activity, evening activity and activity at noon. Individual behavior can be reduced to weights on these four components. We do not observe any clear emergent categories of people based on the weights, but individuals are rather placed on a continuous spectrum according to the timings of their activities. High loads on morning and night components highly correlate with going to bed and waking up times. Our work points towards a data-driven way of categorizing people based on their full daily and weekly rhythms of activity and behavior, rather than focusing mainly on the timing of their sleeping periods. △ Less

Submitted 21 September, 2020; originally announced September 2020.

Going beyond communication intensity for estimating tie strengths in social networks

Authors: Javier Ureña-Carrion, Jari Saramäki, Mikko Kivelä

Abstract: Even though the concept of tie strength is central in social network analysis, it is difficult to quantify how strong social ties are. One typical way of estimating tie strength in data-driven studies has been to simply count the total number or duration of contacts between two people. This, however, disregards many features that can be extracted from the rich data sets used for social network rec… ▽ More Even though the concept of tie strength is central in social network analysis, it is difficult to quantify how strong social ties are. One typical way of estimating tie strength in data-driven studies has been to simply count the total number or duration of contacts between two people. This, however, disregards many features that can be extracted from the rich data sets used for social network reconstruction. Here, we focus on contact data with temporal information. We systematically study how features of the contact time series are related to topological features usually associated with tie strength. We analyze a large mobile-phone dataset and measure a number of properties of the call time series for each tie, and use these to predict the so-called neighbourhood overlap, a feature related to strong ties in the sociological literature. We observe a strong relationship between temporal features and the neighbourhood overlap, with many features outperforming simple contact counts. Features that stand out include the number of days with calls, number of bursty cascades, typical times of contacts, and temporal stability. Our results suggest that these measures could be adapted for use in social network construction and indicate that the best results can be achieved by combining multiple temporal features. △ Less

Submitted 28 July, 2020; originally announced July 2020.

Comments: 15 pages, 6 figures on main text + 17 pages of supplementary informaiton (one pdf). Submitted to EPJ Data Science. Conference talk on NetSci 2020

Weighted temporal event graphs

Authors: Jari Saramäki, Mikko Kivelä, Márton Karsai

Abstract: The times of temporal-network events and their correlations contain information on the function of the network and they influence dynamical processes taking place on it. To extract information out of correlated event times, techniques such as the analysis of temporal motifs have been developed. We discuss a recently-introduced, more general framework that maps temporal-network structure into stati… ▽ More The times of temporal-network events and their correlations contain information on the function of the network and they influence dynamical processes taking place on it. To extract information out of correlated event times, techniques such as the analysis of temporal motifs have been developed. We discuss a recently-introduced, more general framework that maps temporal-network structure into static graphs while retaining information on time-respecting paths and the time differences between their consequent events. This framework builds on weighted temporal event graphs: directed, acyclic graphs (DAGs) that contain a superposition of all temporal paths. We introduce the reader to the temporal event-graph mapping and associated computational methods and illustrate its use by applying the framework to temporal-network percolation. △ Less

Submitted 9 December, 2019; originally announced December 2019.

Journal ref: Temporal Network Theory, 107-128, Springer-Nature, New York (2019)

Multichannel social signatures and persistent features of ego networks

Authors: S. Heydari, S. G. B. Roberts, R. I. M. Dunbar, J. Saramäki

Abstract: The structure of egocentric networks reflects the way people balance their need for strong, emotionally intense relationships and a diversity of weaker ties. Egocentric network structure can be quantified with 'social signatures', which describe how people distribute their communication effort across the members (alters) of their personal networks. Social signatures based on call data have indicat… ▽ More The structure of egocentric networks reflects the way people balance their need for strong, emotionally intense relationships and a diversity of weaker ties. Egocentric network structure can be quantified with 'social signatures', which describe how people distribute their communication effort across the members (alters) of their personal networks. Social signatures based on call data have indicated that people mostly communicate with a few close alters; they also have persistent, distinct signatures. To examine if these results hold for other channels of communication, here we compare social signatures built from call and text message data, and develop a way of constructing mixed social signatures using both channels. We observe that all types of signatures display persistent individual differences that remain stable despite the turnover in individual alters. We also show that call, text, and mixed signatures resemble one another both at the population level and at the level of individuals. The consistency of social signatures across individuals for different channels of communication is surprising because the choice of channel appears to be alter-specific with no clear overall pattern, and ego networks constructed from calls and texts overlap only partially in terms of alters. These results demonstrate individuals vary in how they allocate their communication effort across their personal networks and this variation is persistent over time and across different channels of communication. △ Less

Submitted 7 June, 2018; originally announced June 2018.

Journal ref: Applied Network Science 3.1 (2018): 8

Social Network Differences of Chronotypes Identified from Mobile Phone Data

Authors: Talayeh Aledavood, Sune Lehmann, Jari Saramäki

Abstract: Human activity follows an approximately 24-hour day-night cycle, but there is significant individual variation in awake and sleep times. Individuals with circadian rhythms at the extremes can be categorized into two chronotypes: "larks", those who wake up and go to sleep early, and "owls", those who stay up and wake up late. It is well established that a person's chronotype can affect their activi… ▽ More Human activity follows an approximately 24-hour day-night cycle, but there is significant individual variation in awake and sleep times. Individuals with circadian rhythms at the extremes can be categorized into two chronotypes: "larks", those who wake up and go to sleep early, and "owls", those who stay up and wake up late. It is well established that a person's chronotype can affect their activities and health. However, less is known on the effects of chronotypes on the social behavior, even though it is evident that social interactions require coordinated timings. To study how chronotypes relate to social behavior, we use data collected using a smartphone app on a population of more than seven hundred volunteer students to simultaneously determine their chronotypes and social network structure. We find that owls maintain larger personal networks, albeit with less time spent per contact. On average, owls are more central in the social network of students than larks, frequently occupying the dense core of the network. Owls also display strong homophily, as seen in an unexpectedly large number of social ties connecting owls to owls. △ Less

Submitted 19 September, 2017; originally announced September 2017.

Mapping temporal-network percolation to weighted, static event graphs

Authors: Mikko Kivelä, Jordan Cambe, Jari Saramäki, Márton Karsai

Abstract: Many processes of spreading and diffusion take place on temporal networks, and their outcomes are influenced by correlations in the times of contact. These correlations have a particularly strong influence on processes where the spreading agent has a limited lifetime at nodes: disease spreading (recovery time), diffusion of rumors (lifetime of information), and passenger routing (maximum acceptabl… ▽ More Many processes of spreading and diffusion take place on temporal networks, and their outcomes are influenced by correlations in the times of contact. These correlations have a particularly strong influence on processes where the spreading agent has a limited lifetime at nodes: disease spreading (recovery time), diffusion of rumors (lifetime of information), and passenger routing (maximum acceptable time between transfers). Here, we introduce weighted event graphs as a powerful and fast framework for studying connectivity determined by time-respecting paths where the allowed waiting times between contacts have an upper limit. We study percolation on the weighted event graphs and in the underlying temporal networks, with simulated and real-world networks. We show that this type of temporal-network percolation is analogous to directed percolation, and that it can be characterized by multiple order parameters. △ Less

Submitted 17 September, 2017; originally announced September 2017.

Comments: 12 pages, 3 figures

Graph coarse-graining reveals differences in the module-level structure of functional brain networks

Authors: Rainer Kujala, Enrico Glerean, Raj Kumar Pan, Iiro P. Jääskeläinen, Mikko Sams, Jari Saramäki

Abstract: Network analysis is rapidly becoming a standard tool for studying functional magnetic resonance imaging (fMRI) data. In this framework, different brain areas are mapped to the nodes of a network, whose links depict functional dependencies between the areas. The sizes of the areas that the nodes portray vary between studies. Recently, it has been recommended that the original volume elements, voxel… ▽ More Network analysis is rapidly becoming a standard tool for studying functional magnetic resonance imaging (fMRI) data. In this framework, different brain areas are mapped to the nodes of a network, whose links depict functional dependencies between the areas. The sizes of the areas that the nodes portray vary between studies. Recently, it has been recommended that the original volume elements, voxels, of the imaging experiment should be used as the network nodes to avoid artefacts and biases. However, this results in a large numbers of nodes and links, and the sheer amount of detail may obscure important network features that are manifested on larger scales. One fruitful approach to detecting such features is to partition networks into modules, i.e. groups of nodes that are densely connected internally but have few connections between them. However, attempting to understand how functional networks differ by simply comparing their individual modular structures can be a daunting task, and results may be hard to interpret. We show that instead of comparing different partitions, it is beneficial to analyze differences in the connectivity between and within the very same modules in networks obtained under different conditions. We develop a network coarse-graining methodology that provides easily interpretable results and allows assessing the statistical significance of observed differences. The feasibility of the method is demonstrated by analyzing fMRI data recorded from 13 healthy subjects during rest and movie viewing. While independent partitioning of the networks corresponding to the the two conditions yields few insights on their differences, network coarse-graining allows us to pinpoint e.g. the increased number of intra-module links within the visual cortex during movie viewing. △ Less

Submitted 29 May, 2017; originally announced May 2017.

Comments: Manuscript + Supplementary materials

Journal ref: European Journal of Neuroscience, 2016, 44, 2673

Ranking influential spreaders is an ill-defined problem

Authors: Jain Gu, Sungmin Lee, Jari Saramäki, Petter Holme

Abstract: Finding influential spreaders of information and disease in networks is an important theoretical problem, and one of considerable recent interest. It has been almost exclusively formulated as a node-ranking problem -- methods for identifying influential spreaders rank nodes according to how influential they are. In this work, we show that the ranking approach does not necessarily work: the set of… ▽ More Finding influential spreaders of information and disease in networks is an important theoretical problem, and one of considerable recent interest. It has been almost exclusively formulated as a node-ranking problem -- methods for identifying influential spreaders rank nodes according to how influential they are. In this work, we show that the ranking approach does not necessarily work: the set of most influential nodes depends on the number of nodes in the set. Therefore, the set of $n$ most important nodes to vaccinate does not need to have any node in common with the set of $n+1$ most important nodes. We propose a method for quantifying the extent and impact of this phenomenon, and show that it is common in both empirical and model networks. △ Less

Submitted 16 March, 2017; originally announced March 2017.

Journal ref: EPL 118 (2017) 68002

Detection of timescales in evolving complex systems

Authors: Richard K. Darst, Clara Granell, Alex Arenas, Sergio Gómez, Jari Saramäki, Santo Fortunato

Abstract: Most complex systems are intrinsically dynamic in nature. The evolution of a dynamic complex system is typically represented as a sequence of snapshots, where each snapshot describes the configuration of the system at a particular instant of time. Then, one may directly follow how the snapshots evolve in time, or aggregate the snapshots within some time intervals to form representative "slices" of… ▽ More Most complex systems are intrinsically dynamic in nature. The evolution of a dynamic complex system is typically represented as a sequence of snapshots, where each snapshot describes the configuration of the system at a particular instant of time. Then, one may directly follow how the snapshots evolve in time, or aggregate the snapshots within some time intervals to form representative "slices" of the evolution of the system configuration. This is often done with constant intervals, whose duration is based on arguments on the nature of the system and of its dynamics. A more refined approach would be to consider the rate of activity in the system to perform a separation of timescales. However, an even better alternative would be to define dynamic intervals that match the evolution of the system's configuration. To this end, we propose a method that aims at detecting evolutionary changes in the configuration of a complex system, and generates intervals accordingly. We show that evolutionary timescales can be identified by looking for peaks in the similarity between the sets of events on consecutive time intervals of data. Tests on simple toy models reveal that the technique is able to detect evolutionary timescales of time-varying data both when the evolution is smooth as well as when it changes sharply. This is further corroborated by analyses of several real datasets. Our method is scalable to extremely large datasets and is computationally efficient. This allows a quick, parameter-free detection of multiple timescales in the evolution of a complex system. △ Less

Submitted 4 April, 2016; originally announced April 2016.

Comments: 17 pages, 7 figures

Journal ref: Scientific Reports 6 (2016) 39713

Two betweenness centrality measures based on Randomized Shortest Paths

Authors: Ilkka Kivimäki, Bertrand Lebichot, Jari Saramäki, Marco Saerens

Abstract: This paper introduces two new closely related betweenness centrality measures based on the Randomized Shortest Paths (RSP) framework, which fill a gap between traditional network centrality measures based on shortest paths and more recent methods considering random walks or current flows. The framework defines Boltzmann probability distributions over paths of the network which focus on the shortes… ▽ More This paper introduces two new closely related betweenness centrality measures based on the Randomized Shortest Paths (RSP) framework, which fill a gap between traditional network centrality measures based on shortest paths and more recent methods considering random walks or current flows. The framework defines Boltzmann probability distributions over paths of the network which focus on the shortest paths, but also take into account longer paths depending on an inverse temperature parameter. RSP's have previously proven to be useful in defining distance measures on networks. In this work we study their utility in quantifying the importance of the nodes of a network. The proposed RSP betweenness centralities combine, in an optimal way, the ideas of using the shortest and purely random paths for analysing the roles of network nodes, avoiding issues involving these two paradigms. We present the derivations of these measures and how they can be computed in an efficient way. In addition, we show with real world examples the potential of the RSP betweenness centralities in identifying interesting nodes of a network that more traditional methods might fail to notice. △ Less

Submitted 2 February, 2016; v1 submitted 10 September, 2015; originally announced September 2015.

Comments: Minor updates; published in Scientific Reports

Journal ref: Scientific Reports 6, Article number: 19668 (2016)

Exploring Temporal Networks with Greedy Walks

Authors: Jari Saramaki, Petter Holme

Abstract: Temporal networks come with a wide variety of heterogeneities, from burstiness of event sequences to correlations between timings of node and link activations. In this paper, we set to explore the latter by using greedy walks as probes of temporal network structure. Given a temporal network (a sequence of contacts), greedy walks proceed from node to node by always following the first available con… ▽ More Temporal networks come with a wide variety of heterogeneities, from burstiness of event sequences to correlations between timings of node and link activations. In this paper, we set to explore the latter by using greedy walks as probes of temporal network structure. Given a temporal network (a sequence of contacts), greedy walks proceed from node to node by always following the first available contact. Because of this, their structure is particularly sensitive to temporal-topological patterns involving repeated contacts between sets of nodes. This becomes evident in their small coverage per step as compared to a temporal reference model -- in empirical temporal networks, greedy walks often get stuck within small sets of nodes because of correlated contact patterns. While this may also happen in static networks that have pronounced community structure, the use of the temporal reference model takes the underlying static network structure out of the equation and indicates that there is a purely temporal reason for the observations. Further analysis of the structure of greedy walks indicates that burst trains, sequences of repeated contacts between node pairs, are the dominant factor. However, there are larger patterns too, as shown with non-backtracking greedy walks. We proceed further to study the entropy rates of greedy walks, and show that the sequences of visited nodes are more structured and predictable in original data as compared to temporally uncorrelated references. Taken together, these results indicate a richness of correlated temporal-topological patterns in temporal networks. △ Less

Submitted 2 November, 2015; v1 submitted 4 August, 2015; originally announced August 2015.

On the Digital Daily Cycles of Individuals

Authors: Talayeh Aledavood, Sune Lehmann, Jari Saramäki

Abstract: Humans, like almost all animals, are phase-locked to the diurnal cycle. Most of us sleep at night and are active through the day. Because we have evolved to function with this cycle, the circadian rhythm is deeply ingrained and even detectable at the biochemical level. However, within the broader day-night pattern, there are individual differences: e.g., some of us are intrinsically morning-active… ▽ More Humans, like almost all animals, are phase-locked to the diurnal cycle. Most of us sleep at night and are active through the day. Because we have evolved to function with this cycle, the circadian rhythm is deeply ingrained and even detectable at the biochemical level. However, within the broader day-night pattern, there are individual differences: e.g., some of us are intrinsically morning-active, while others prefer evenings. In this article, we look at digital daily cycles: circadian patterns of activity viewed through the lens of auto-recorded data of communication and online activity. We begin at the aggregate level, discuss earlier results, and illustrate differences between population-level daily rhythms in different media. Then we move on to the individual level, and show that there is a strong individual-level variation beyond averages: individuals typically have their distinctive daily pattern that persists in time. We conclude by discussing the driving forces behind these signature daily patterns, from personal traits (morningness/eveningness) to variation in activity level and external constraints, and outline possibilities for future research. △ Less

Submitted 29 July, 2015; originally announced July 2015.

From calls to communities: a model for time varying social networks

Authors: Guillaume Laurent, Jari Saramäki, Márton Karsai

Abstract: Social interactions vary in time and appear to be driven by intrinsic mechanisms, which in turn shape the emerging structure of the social network. Large-scale empirical observations of social interaction structure have become possible only recently, and modelling their dynamics is an actual challenge. Here we propose a temporal network model which builds on the framework of activity-driven time-v… ▽ More Social interactions vary in time and appear to be driven by intrinsic mechanisms, which in turn shape the emerging structure of the social network. Large-scale empirical observations of social interaction structure have become possible only recently, and modelling their dynamics is an actual challenge. Here we propose a temporal network model which builds on the framework of activity-driven time-varying networks with memory. The model also integrates key mechanisms that drive the formation of social ties - social reinforcement, focal closure and cyclic closure, which have been shown to give rise to community structure and the global connectedness of the network. We compare the proposed model with a real-world time-varying network of mobile phone communication and show that they share several characteristics from heterogeneous degrees and weights to rich community structure. Further, the strong and weak ties that emerge from the model follow similar weight-topology correlations as real-world social networks, including the role of weak ties. △ Less

Submitted 1 June, 2015; originally announced June 2015.

Comments: 10 pages, 5 figures

From seconds to months: multi-scale dynamics of mobile telephone calls

Authors: Jari Saramaki, Esteban Moro

Abstract: Big Data on electronic records of social interactions allow approaching human behaviour and sociality from a quantitative point of view with unforeseen statistical power. Mobile telephone Call Detail Records (CDRs), automatically collected by telecom operators for billing purposes, have proven especially fruitful for understanding one-to-one communication patterns as well as the dynamics of social… ▽ More Big Data on electronic records of social interactions allow approaching human behaviour and sociality from a quantitative point of view with unforeseen statistical power. Mobile telephone Call Detail Records (CDRs), automatically collected by telecom operators for billing purposes, have proven especially fruitful for understanding one-to-one communication patterns as well as the dynamics of social networks that are reflected in such patterns. We present an overview of empirical results on the multi-scale dynamics of social dynamics and networks inferred from mobile telephone calls. We begin with the shortest timescales and fastest dynamics, such as burstiness of call sequences between individuals, and "zoom out" towards longer temporal and larger structural scales, from temporal motifs formed by correlated calls between multiple individuals to long-term dynamics of social groups. We conclude this overview with a future outlook. △ Less

Submitted 7 April, 2015; originally announced April 2015.

Journal ref: Eur. Phys. J. B (2015) 88: 164

Reorganization of functionally connected brain subnetworks in high-functioning autism

Authors: Enrico Glerean, Raj Kumar Pan, Juha Salmi, Rainer Kujala, Juha Lahnakoski, Ulrika Roine, Lauri Nummenmaa, Sami Leppämäki, Taina Nieminen-von Wendt, Pekka Tani, Jari Saramäki, Mikko Sams, Iiro P. Jääskeläinen

Abstract: Background: Previous functional connectivity studies have found both hypo- and hyper-connectivity in brains of individuals having autism spectrum disorder (ASD). Here we studied abnormalities in functional brain subnetworks in high-functioning individuals with ASD during free viewing of a movie containing social cues and interactions. Methods: Thirteen subjects with ASD and 13 matched-pair control… ▽ More Background: Previous functional connectivity studies have found both hypo- and hyper-connectivity in brains of individuals having autism spectrum disorder (ASD). Here we studied abnormalities in functional brain subnetworks in high-functioning individuals with ASD during free viewing of a movie containing social cues and interactions. Methods: Thirteen subjects with ASD and 13 matched-pair controls watched a 68 minutes movie during functional magnetic resonance imaging. For each subject, we computed Pearson`s correlation between haemodynamic time-courses of each pair of 6-mm isotropic voxels. From the whole-brain functional networks, we derived individual and group-level subnetworks using graph theory. Scaled inclusivity was then calculated between all subject pairs to estimate intersubject similarity of connectivity structure of each subnetwork. Additional 27 individuals with ASD from the ABIDE resting-state database were included to test the reproducibility of the results. Results: Between-group differences were observed in the composition of default-mode and a ventro-temporal-limbic (VTL) subnetwork. The VTL subnetwork included amygdala, striatum, thalamus, parahippocampal, fusiform, and inferior temporal gyri. Further, VTL subnetwork similarity between subject pairs correlated significantly with similarity of symptom gravity measured with autism quotient. This correlation was observed also within the controls, and in the reproducibility dataset with ADI-R and ADOS scores. Conclusions: Reorganization of functional subnetworks in individuals with ASD clarifies the mixture of hypo- and hyper-connectivity findings. Importantly, only the functional organization of the VTL subnetwork emerges as a marker of inter-individual similarities that co-vary with behavioral measures across all participants. These findings suggest a pivotal role of ventro-temporal and limbic systems in autism. △ Less

Submitted 16 March, 2015; originally announced March 2015.

Daily rhythms in mobile telephone communication

Authors: Talayeh Aledavood, Eduardo López, Sam G. B. Roberts, Felix Reed-Tsochas, Esteban Moro, Robin I. M. Dunbar, Jari Saramäki

Abstract: Circadian rhythms are known to be important drivers of human activity and the recent availability of electronic records of human behaviour has provided fine-grained data of temporal patterns of activity on a large scale. Further, questionnaire studies have identified important individual differences in circadian rhythms, with people broadly categorised into morning-like or evening-like individuals… ▽ More Circadian rhythms are known to be important drivers of human activity and the recent availability of electronic records of human behaviour has provided fine-grained data of temporal patterns of activity on a large scale. Further, questionnaire studies have identified important individual differences in circadian rhythms, with people broadly categorised into morning-like or evening-like individuals. However, little is known about the social aspects of these circadian rhythms, or how they vary across individuals. In this study we use a unique 18-month dataset that combines mobile phone calls and questionnaire data to examine individual differences in the daily rhythms of mobile phone activity. We demonstrate clear individual differences in daily patterns of phone calls, and show that these individual differences are persistent despite a high degree of turnover in the individuals' social networks. Further, women's calls were longer than men's calls, especially during the evening and at night, and these calls were typically focused on a small number of emotionally intense relationships. These results demonstrate that individual differences in circadian rhythms are not just related to broad patterns of morningness and eveningness, but have a strong social component, in directing phone calls to specific individuals at specific times of day. △ Less

Submitted 24 February, 2015; originally announced February 2015.

Journal ref: PLoS ONE 10(9) e0138098 (2015)

Temporal network sparsity and the slowing down of spreading

Authors: Juan Ignacio Perotti, Hang-Hyun Jo, Petter Holme, Jari Saramäki

Abstract: Interactions in time-varying complex systems are often very heterogeneous at the topological level (who interacts with whom) and at the temporal level (when interactions occur and how often). While it is known that temporal heterogeneities often have strong effects on dynamical processes, e.g. the burstiness of contact sequences is associated with slower spreading dynamics, the picture is far from… ▽ More Interactions in time-varying complex systems are often very heterogeneous at the topological level (who interacts with whom) and at the temporal level (when interactions occur and how often). While it is known that temporal heterogeneities often have strong effects on dynamical processes, e.g. the burstiness of contact sequences is associated with slower spreading dynamics, the picture is far from complete. In this paper, we show that temporal heterogeneities result in temporal sparsity} at the time scale of average inter-event times, and that temporal sparsity determines the amount of slowdown of Susceptible-Infectious (SI) spreading dynamics on temporal networks. This result is based on the analysis of several empirical temporal network data sets. An approximate solution for a simple network model confirms the association between temporal sparsity and slowdown of SI spreading dynamics. Since deterministic SI spreading always follows the fastest temporal paths, our results generalize -- paths are slower to traverse because of temporal sparsity, and therefore all dynamical processes are slower as well. △ Less

Submitted 20 November, 2014; originally announced November 2014.

Spatial patterns of close relationships across the lifespan

Authors: Hang-Hyun Jo, Jari Saramäki, Robin I. M. Dunbar, Kimmo Kaski

Abstract: The dynamics of close relationships is important for understanding the migration patterns of individual life-courses. The bottom-up approach to this subject by social scientists has been limited by sample size, while the more recent top-down approach using large-scale datasets suffers from a lack of detail about the human individuals. We incorporate the geographic and demographic information of mi… ▽ More The dynamics of close relationships is important for understanding the migration patterns of individual life-courses. The bottom-up approach to this subject by social scientists has been limited by sample size, while the more recent top-down approach using large-scale datasets suffers from a lack of detail about the human individuals. We incorporate the geographic and demographic information of millions of mobile phone users with their communication patterns to study the dynamics of close relationships and its effect in their life-course migration. We demonstrate how the close age- and sex-biased dyadic relationships are correlated with the geographic proximity of the pair of individuals, e.g., young couples tend to live further from each other than old couples. In addition, we find that emotionally closer pairs are living geographically closer to each other. These findings imply that the life-course framework is crucial for understanding the complex dynamics of close relationships and their effect on the migration patterns of human individuals. △ Less

Submitted 17 September, 2014; v1 submitted 18 July, 2014; originally announced July 2014.

Comments: 9 pages, 7 figures

Journal ref: Scientific Reports 4, 6988 (2014)

Inferring human mobility using communication patterns

Authors: Vasyl Palchykov, Marija Mitrović, Hang-Hyun Jo, Jari Saramäki, Raj Kumar Pan

Abstract: Understanding the patterns of mobility of individuals is crucial for a number of reasons, from city planning to disaster management. There are two common ways of quantifying the amount of travel between locations: by direct observations that often involve privacy issues, e.g., tracking mobile phone locations, or by estimations from models. Typically, such models build on accurate knowledge of the… ▽ More Understanding the patterns of mobility of individuals is crucial for a number of reasons, from city planning to disaster management. There are two common ways of quantifying the amount of travel between locations: by direct observations that often involve privacy issues, e.g., tracking mobile phone locations, or by estimations from models. Typically, such models build on accurate knowledge of the population size at each location. However, when this information is not readily available, their applicability is rather limited. As mobile phones are ubiquitous, our aim is to investigate if mobility patterns can be inferred from aggregated mobile phone call data alone. Using data released by Orange for Ivory Coast, we show that human mobility is well predicted by a simple model based on the frequency of mobile phone calls between two locations and their geographical distance. We argue that the strength of the model comes from directly incorporating the social dimension of mobility. Furthermore, as only aggregated call data is required, the model helps to avoid potential privacy problems. △ Less

Submitted 22 August, 2014; v1 submitted 30 April, 2014; originally announced April 2014.

Comments: 7 pages, 3 figures; Published version

Journal ref: Sci. Rep. 4, 6174 (2014)

Effects of temporal correlations on cascades: Threshold models on temporal networks

Authors: Ville-Pekka Backlund, Jari Saramäki, Raj Kumar Pan

Abstract: A person's decision to adopt an idea or product is often driven by the decisions of peers, mediated through a network of social ties. A common way of modeling adoption dynamics is to use threshold models, where a node may become an adopter given a high enough rate of contacts with adopted neighbors. We study the dynamics of threshold models that take both the network topology and the timings of co… ▽ More A person's decision to adopt an idea or product is often driven by the decisions of peers, mediated through a network of social ties. A common way of modeling adoption dynamics is to use threshold models, where a node may become an adopter given a high enough rate of contacts with adopted neighbors. We study the dynamics of threshold models that take both the network topology and the timings of contacts into account, using empirical contact sequences as substrates. The models are designed such that adoption is driven by the number of contacts with different adopted neighbors within a chosen time. We find that while some networks support cascades leading to network-level adoption, some do not: the propagation of adoption depends on several factors from the frequency of contacts to burstiness and timing correlations of contact sequences. More specifically, burstiness is seen to suppress cascades sizes when compared to randomised contact timings, while timing correlations between contacts on adjacent links facilitate cascades. △ Less

Submitted 27 June, 2014; v1 submitted 5 March, 2014; originally announced March 2014.

Comments: 9 pages, 7 figures, Published version

Journal ref: Phys. Rev. E 89, 062815 (2014)

Temporal motifs reveal homophily, gender-specific patterns and group talk in mobile communication networks

Authors: Lauri Kovanen, Kimmo Kaski, János Kertész, Jari Saramäki

Abstract: Electronic communication records provide detailed information about temporal aspects of human interaction. Previous studies have shown that individuals' communication patterns have complex temporal structure, and that this structure has system-wide effects. In this paper we use mobile phone records to show that interaction patterns involving multiple individuals have non-trivial temporal structure… ▽ More Electronic communication records provide detailed information about temporal aspects of human interaction. Previous studies have shown that individuals' communication patterns have complex temporal structure, and that this structure has system-wide effects. In this paper we use mobile phone records to show that interaction patterns involving multiple individuals have non-trivial temporal structure that cannot be deduced from a network presentation where only interaction frequencies are taken into account. We apply a recently introduced method, temporal motifs, to identify interaction patterns in a temporal network where nodes have additional attributes such as gender and age. We then develop a null model that allows identifying differences between various types of nodes so that these differences are independent of the network based on interaction frequencies. We find gender-related differences in communication patters, and show the existence of temporal homophily, the tendency of similar individuals to participate in interaction patterns beyond what would be expected on the basis of the network structure alone. We also show that temporal patterns differ between dense and sparse parts of the network. Because this result is independent of edge weights, it can be considered as an extension of Granovetter's hypothesis to temporal networks. △ Less

Submitted 11 February, 2013; originally announced February 2013.

Comments: 8 pages, 3 figures (SI: 20 pages, 18 figures)

The evolution of interdisciplinarity in physics research

Authors: Raj Kumar Pan, Sitabhra Sinha, Kimmo Kaski, Jari Saramäki

Abstract: Science, being a social enterprise, is subject to fragmentation into groups that focus on specialized areas or topics. Often new advances occur through cross-fertilization of ideas between sub-fields that otherwise have little overlap as they study dissimilar phenomena using different techniques. Thus to explore the nature and dynamics of scientific progress one needs to consider the large-scale o… ▽ More Science, being a social enterprise, is subject to fragmentation into groups that focus on specialized areas or topics. Often new advances occur through cross-fertilization of ideas between sub-fields that otherwise have little overlap as they study dissimilar phenomena using different techniques. Thus to explore the nature and dynamics of scientific progress one needs to consider the large-scale organization and interactions between different subject areas. Here, we study the relationships between the sub-fields of Physics using the Physics and Astronomy Classification Scheme (PACS) codes employed for self-categorization of articles published over the past 25 years (1985-2009). We observe a clear trend towards increasing interactions between the different sub-fields. The network of sub-fields also exhibits core-periphery organization, the nucleus being dominated by Condensed Matter and General Physics. However, over time Interdisciplinary Physics is steadily increasing its share in the network core, reflecting a shift in the overall trend of Physics research. △ Less

Submitted 16 August, 2012; v1 submitted 1 June, 2012; originally announced June 2012.

Comments: Published version, 10 pages, 8 figures + Supplementary Information

Journal ref: Scientific Reports 2, 551 (2012)

The persistence of social signatures in human communication

Authors: J. Saramaki, E. A. Leicht, E. Lopez, S. G. B. Roberts, F. Reed-Tsochas, R. I. M. Dunbar

Abstract: The social network maintained by a focal individual, or ego, is intrinsically dynamic and typically exhibits some turnover in membership over time as personal circumstances change. However, the consequences of such changes on the distribution of an ego's network ties are not well understood. Here we use a unique 18-month data set that combines mobile phone calls and survey data to track changes in… ▽ More The social network maintained by a focal individual, or ego, is intrinsically dynamic and typically exhibits some turnover in membership over time as personal circumstances change. However, the consequences of such changes on the distribution of an ego's network ties are not well understood. Here we use a unique 18-month data set that combines mobile phone calls and survey data to track changes in the ego networks and communication patterns of students making the transition from school to university or work. Our analysis reveals that individuals display a distinctive and robust social signature, captured by how interactions are distributed across different alters. Notably, for a given ego, these social signatures tend to persist over time, despite considerable turnover in the identity of alters in the ego network. Thus as new network members are added, some old network members are either replaced or receive fewer calls, preserving the overall distribution of calls across network members. This is likely to reflect the consequences of finite resources such as the time available for communication, the cognitive and emotional effort required to sustain close relationships, and the ability to make emotional investments. △ Less

Submitted 16 December, 2013; v1 submitted 25 April, 2012; originally announced April 2012.

Comments: Revised version, SI Appendix added

Journal ref: Proc.Natl.Acad.Sci. U.S.A. 111 (2014) 942-947

Effects of time window size and placement on the structure of aggregated networks

Authors: Gautier Krings, Márton Karsai, Sebastian Bernharsson, Vincent D Blondel, Jari Saramäki

Abstract: Complex networks are often constructed by aggregating empirical data over time, such that a link represents the existence of interactions between the endpoint nodes and the link weight represents the intensity of such interactions within the aggregation time window. The resulting networks are then often considered static. More often than not, the aggregation time window is dictated by the availabi… ▽ More Complex networks are often constructed by aggregating empirical data over time, such that a link represents the existence of interactions between the endpoint nodes and the link weight represents the intensity of such interactions within the aggregation time window. The resulting networks are then often considered static. More often than not, the aggregation time window is dictated by the availability of data, and the effects of its length on the resulting networks are rarely considered. Here, we address this question by studying the structural features of networks emerging from aggregating empirical data over different time intervals, focussing on networks derived from time-stamped, anonymized mobile telephone call records. Our results show that short aggregation intervals yield networks where strong links associated with dense clusters dominate; the seeds of such clusters or communities become already visible for intervals of around one week. The degree and weight distributions are seen to become stationary around a few days and a few weeks, respectively. An aggregation interval of around 30 days results in the stablest similar networks when consecutive windows are compared. For longer intervals, the effects of weak or random links become increasingly stronger, and the average degree of the network keeps growing even for intervals up to 180 days. The placement of the time window is also seen to affect the outcome: for short windows, different behavioural patterns play a role during weekends and weekdays, and for longer windows it is seen that networks aggregated during holiday periods are significantly different. △ Less

Submitted 6 February, 2012; originally announced February 2012.

Comments: 19 pages, 11 figures

Journal ref: EPJ Data Science, 2012, Volume 1, Number 1, 4

Multiscale Analysis of Spreading in a Large Communication Network

Authors: Mikko Kivelä, Raj Kumar Pan, Kimmo Kaski, János Kertész, Jari Saramäki, Márton Karsai

Abstract: In temporal networks, both the topology of the underlying network and the timings of interaction events can be crucial in determining how some dynamic process mediated by the network unfolds. We have explored the limiting case of the speed of spreading in the SI model, set up such that an event between an infectious and susceptible individual always transmits the infection. The speed of this proce… ▽ More In temporal networks, both the topology of the underlying network and the timings of interaction events can be crucial in determining how some dynamic process mediated by the network unfolds. We have explored the limiting case of the speed of spreading in the SI model, set up such that an event between an infectious and susceptible individual always transmits the infection. The speed of this process sets an upper bound for the speed of any dynamic process that is mediated through the interaction events of the network. With the help of temporal networks derived from large scale time-stamped data on mobile phone calls, we extend earlier results that point out the slowing-down effects of burstiness and temporal inhomogeneities. In such networks, links are not permanently active, but dynamic processes are mediated by recurrent events taking place on the links at specific points in time. We perform a multi-scale analysis and pinpoint the importance of the timings of event sequences on individual links, their correlations with neighboring sequences, and the temporal pathways taken by the network-scale spreading process. This is achieved by studying empirically and analytically different characteristic relay times of links, relevant to the respective scales, and a set of temporal reference models that allow for removing selected time-domain correlations one by one. △ Less

Submitted 19 December, 2011; originally announced December 2011.

Journal ref: J. Stat. Mech. (2012) P03005

Temporal Networks

Authors: Petter Holme, Jari Saramäki

Abstract: A great variety of systems in nature, society and technology -- from the web of sexual contacts to the Internet, from the nervous system to power grids -- can be modeled as graphs of vertices coupled by edges. The network structure, describing how the graph is wired, helps us understand, predict and optimize the behavior of dynamical systems. In many cases, however, the edges are not continuously… ▽ More A great variety of systems in nature, society and technology -- from the web of sexual contacts to the Internet, from the nervous system to power grids -- can be modeled as graphs of vertices coupled by edges. The network structure, describing how the graph is wired, helps us understand, predict and optimize the behavior of dynamical systems. In many cases, however, the edges are not continuously active. As an example, in networks of communication via email, text messages, or phone calls, edges represent sequences of instantaneous or practically instantaneous contacts. In some cases, edges are active for non-negligible periods of time: e.g., the proximity patterns of inpatients at hospitals can be represented by a graph where an edge between two individuals is on throughout the time they are at the same ward. Like network topology, the temporal structure of edge activations can affect dynamics of systems interacting through the network, from disease contagion on the network of patients to information diffusion over an e-mail network. In this review, we present the emergent field of temporal networks, and discuss methods for analyzing topological and temporal structure and models for elucidating their relation to the behavior of dynamical systems. In the light of traditional network theory, one can see this framework as moving the information of when things happen from the dynamical system on the network, to the network itself. Since fundamental properties, such as the transitivity of edges, do not necessarily hold in temporal networks, many of these methods need to be quite different from those for static networks. △ Less

Submitted 15 December, 2011; v1 submitted 8 August, 2011; originally announced August 2011.

Journal ref: Phys. Rep. 519, 97-125 (2012)

Temporal motifs in time-dependent networks

Authors: Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, Jari Saramäki

Abstract: Temporal networks are commonly used to represent systems where connections between elements are active only for restricted periods of time, such as networks of telecommunication, neural signal processing, biochemical reactions and human social interactions. We introduce the framework of temporal motifs to study the mesoscale topological-temporal structure of temporal networks in which the events o… ▽ More Temporal networks are commonly used to represent systems where connections between elements are active only for restricted periods of time, such as networks of telecommunication, neural signal processing, biochemical reactions and human social interactions. We introduce the framework of temporal motifs to study the mesoscale topological-temporal structure of temporal networks in which the events of nodes do not overlap in time. Temporal motifs are classes of similar event sequences, where the similarity refers not only to topology but also to the temporal order of the events. We provide a mapping from event sequences to colored directed graphs that enables an efficient algorithm for identifying temporal motifs. We discuss some aspects of temporal motifs, including causality and null models, and present basic statistics of temporal motifs in a large mobile call network. △ Less

Submitted 10 October, 2011; v1 submitted 28 July, 2011; originally announced July 2011.

Comments: 18 pages, 8 figures; minor revisions

Journal ref: J. Stat. Mech. (2011) P11005

The strength of strong ties in scientific collaboration networks

Authors: Raj Kumar Pan, Jari Saramäki

Abstract: Network topology and its relationship to tie strengths may hinder or enhance the spreading of information in social networks. We study the correlations between tie strengths and topology in networks of scientific collaboration, and show that these are very different from ordinary social networks. For the latter, it has earlier been shown that strong ties are associated with dense network neighborh… ▽ More Network topology and its relationship to tie strengths may hinder or enhance the spreading of information in social networks. We study the correlations between tie strengths and topology in networks of scientific collaboration, and show that these are very different from ordinary social networks. For the latter, it has earlier been shown that strong ties are associated with dense network neighborhoods, while weaker ties act as bridges between these. Because of this, weak links act as bottlenecks for the diffusion of information. We show that on the contrary, in co-authorship networks dense local neighborhoods mainly consist of weak links, whereas strong links are more important for overall connectivity. The important role of strong links is further highlighted in simulations of information spreading, where their topological position is seen to dramatically speed up spreading dynamics. Thus, in contrast to ordinary social networks, weight-topology correlations enhance the flow of information across scientific collaboration networks. △ Less

Submitted 11 January, 2012; v1 submitted 26 June, 2011; originally announced June 2011.

Comments: 6 Pages, 6 Figures, Published version, Minor changes, Results also verified using new weight-scheme

Journal ref: Europhys. Lett. 97, 18007 (2012)

Path lengths, correlations, and centrality in temporal networks

Authors: Raj Kumar Pan, Jari Saramäki

Abstract: In temporal networks, where nodes interact via sequences of temporary events, information or resources can only flow through paths that follow the time-ordering of events. Such temporal paths play a crucial role in dynamic processes. However, since networks have so far been usually considered static or quasi-static, the properties of temporal paths are not yet well understood. Building on a defini… ▽ More In temporal networks, where nodes interact via sequences of temporary events, information or resources can only flow through paths that follow the time-ordering of events. Such temporal paths play a crucial role in dynamic processes. However, since networks have so far been usually considered static or quasi-static, the properties of temporal paths are not yet well understood. Building on a definition and algorithmic implementation of the average temporal distance between nodes, we study temporal paths in empirical networks of human communication and air transport. Although temporal distances correlate with static graph distances, there is a large spread, and nodes that appear close from the static network view may be connected via slow paths or not at all. Differences between static and temporal properties are further highlighted in studies of the temporal closeness centrality. In addition, correlations and heterogeneities in the underlying event sequences affect temporal path lengths, increasing temporal distances in communication networks and decreasing them in the air transport network. △ Less

Submitted 19 July, 2011; v1 submitted 31 January, 2011; originally announced January 2011.

Comments: 10 pages, 8 figures, Published version

Journal ref: Phys. Rev. E 84, 016105 (2011)

Using explosive percolation in analysis of real-world networks

Authors: Raj Kumar Pan, Mikko Kivelä, Jari Saramäki, Kimmo Kaski, János Kertész

Abstract: We apply a variant of the explosive percolation procedure to large real-world networks, and show with finite-size scaling that the university class, ordinary or explosive, of the resulting percolation transition depends on the structural properties of the network as well as the number of unoccupied links considered for comparison in our procedure. We observe that in our social networks, the percol… ▽ More We apply a variant of the explosive percolation procedure to large real-world networks, and show with finite-size scaling that the university class, ordinary or explosive, of the resulting percolation transition depends on the structural properties of the network as well as the number of unoccupied links considered for comparison in our procedure. We observe that in our social networks, the percolation clusters close to the critical point are related to the community structure. This relationship is further highlighted by applying the procedure to model networks with pre-defined communities. △ Less

Submitted 18 April, 2011; v1 submitted 15 October, 2010; originally announced October 2010.

Comments: 6 pages, 4 figures. Published version. Elongated to include the results and figures of finite-size scaling and modularity analysis

Journal ref: Phys. Rev. E 83, 046112 (2011)

Small But Slow World: How Network Topology and Burstiness Slow Down Spreading

Authors: M. Karsai, M. Kivelä, R. K. Pan, K. Kaski, J. Kertész, A. -L. Barabási, J. Saramäki

Abstract: Communication networks show the small-world property of short paths, but the spreading dynamics in them turns out slow. We follow the time evolution of information propagation through communication networks by using the SI model with empirical data on contact sequences. We introduce null models where the sequences are randomly shuffled in different ways, enabling us to distinguish between the cont… ▽ More Communication networks show the small-world property of short paths, but the spreading dynamics in them turns out slow. We follow the time evolution of information propagation through communication networks by using the SI model with empirical data on contact sequences. We introduce null models where the sequences are randomly shuffled in different ways, enabling us to distinguish between the contributions of different impeding effects. The slowing down of spreading is found to be caused mostly by weight-topology correlations and the bursty activity patterns of individuals. △ Less

Submitted 22 August, 2010; v1 submitted 10 June, 2010; originally announced June 2010.

Journal ref: Phys. Rev. E 83, 025102(R) (2011)

Communities and beyond: mesoscopic analysis of a large social network with complementary methods

Authors: Gergely Tibely, Lauri Kovanen, Marton Karsai, Kimmo Kaski, Janos Kertesz, Jari Saramaki

Abstract: Community detection methods have so far been tested mostly on small empirical networks and on synthetic benchmarks. Much less is known about their performance on large real-world networks, which nonetheless are a significant target for application. We analyze the performance of three state-of-the-art community detection methods by using them to identify communities in a large social network constr… ▽ More Community detection methods have so far been tested mostly on small empirical networks and on synthetic benchmarks. Much less is known about their performance on large real-world networks, which nonetheless are a significant target for application. We analyze the performance of three state-of-the-art community detection methods by using them to identify communities in a large social network constructed from mobile phone call records. We find that all methods detect communities that are meaningful in some respects but fall short in others, and that there often is a hierarchical relationship between communities detected by different methods. Our results suggest that community detection methods could be useful in studying the general mesoscale structure of networks, as opposed to only trying to identify dense structures. △ Less

Submitted 8 June, 2011; v1 submitted 2 June, 2010; originally announced June 2010.

Comments: 11 pages, 10 figures. V2: typos corrected, one sentence added. V3: revised version, Appendix added. V4: final published version

Journal ref: Phys. Rev. E 83, 056125 (2011)

Characterizing the community structure of complex networks

Authors: Andrea Lancichinetti, Mikko Kivela, Jari Saramaki, Santo Fortunato

Abstract: Community structure is one of the key properties of complex networks and plays a crucial role in their topology and function. While an impressive amount of work has been done on the issue of community detection, very little attention has been so far devoted to the investigation of communities in real networks. We present a systematic empirical analysis of the statistical properties of communities… ▽ More Community structure is one of the key properties of complex networks and plays a crucial role in their topology and function. While an impressive amount of work has been done on the issue of community detection, very little attention has been so far devoted to the investigation of communities in real networks. We present a systematic empirical analysis of the statistical properties of communities in large information, communication, technological, biological, and social networks. We find that the mesoscopic organization of networks of the same category is remarkably similar. This is reflected in several characteristics of community structure, which can be used as ``fingerprints'' of specific network categories. While community size distributions are always broad, certain categories of networks consist mainly of tree-like communities, while others have denser modules. Average path lengths within communities initially grow logarithmically with community size, but the growth saturates or slows down for communities larger than a characteristic size. This behaviour is related to the presence of hubs within communities, whose roles differ across categories. Also the community embeddedness of nodes, measured in terms of the fraction of links within their communities, has a characteristic distribution for each category. Our findings are verified by the use of two fundamentally different community detection methods. △ Less

Submitted 24 May, 2010; originally announced May 2010.

Comments: 15 pages, 20 figures, 4 tables

Journal ref: PLoS One 5(8), e11976 (2010)

Reciprocity of mobile phone calls

Authors: Lauri Kovanen, Jari Saramaki, Kimmo Kaski

Abstract: We present a study of the reciprocity of human behaviour based on mobile phone usage records. The underlying question is whether human relationships are mutual, in the sense that both are equally active in keeping up the relationship, or is it on the contrary typical that relationships are lopsided, with one party being significantly more active than the other. We study this question with the he… ▽ More We present a study of the reciprocity of human behaviour based on mobile phone usage records. The underlying question is whether human relationships are mutual, in the sense that both are equally active in keeping up the relationship, or is it on the contrary typical that relationships are lopsided, with one party being significantly more active than the other. We study this question with the help of a mobile phone data set consisting of all mobile phone calls between 5.3 million customers of a single mobile phone operator. It turns out that lopsided relations are indeed quite common, to the extent that the variation cannot be explained by simple random deviations or by variations in personal activity. We also show that there is no non-trivial correlation between reciprocity and local network density. △ Less

Submitted 3 February, 2010; originally announced February 2010.

Comments: 12 pages, 7 figures. Accepted for publication in Dynamics of Socio-Economic Systems

Journal ref: Dynamics of Socio-Economic Systems, Vol. 2, No. 2, pp. 138-151 (2011)

Dynamics of latent voters

Authors: Renaud Lambiotte, Jari Saramaki, Vincent D. Blondel

Abstract: We study the effect of latency on binary-choice opinion formation models. Latency is introduced into the models as an additional dynamic rule: after a voter changes its opinion, it enters a waiting period of stochastic length where no further changes take place. We first focus on the voter model and show that as a result of introducing latency, the average magnetization is not conserved, and the… ▽ More We study the effect of latency on binary-choice opinion formation models. Latency is introduced into the models as an additional dynamic rule: after a voter changes its opinion, it enters a waiting period of stochastic length where no further changes take place. We first focus on the voter model and show that as a result of introducing latency, the average magnetization is not conserved, and the system is driven toward zero magnetization, independently of initial conditions. The model is studied analytically in the mean-field case and by simulations in one dimension. We also address the behavior of the Majority Rule model with added latency, and show that the competition between imitation and latency leads to a rich phenomenology. △ Less

Submitted 10 November, 2008; originally announced November 2008.

Journal ref: Phys. Rev. E 79, 046107 (2009)

Broad lifetime distributions for ordering dynamics in complex networks

Authors: R. Toivonen, X. Castelló, V. M. Eguíluz, J. Saramäki, K. Kaski, M. San Miguel

Abstract: We search for conditions under which a characteristic time scale for ordering dynamics towards either of two absorbing states in a finite complex network of interactions does not exist. With this aim, we study random networks and networks with mesoscale community structure built up from randomly connected cliques. We find that large heterogeneity at the mesoscale level of the network appears to… ▽ More We search for conditions under which a characteristic time scale for ordering dynamics towards either of two absorbing states in a finite complex network of interactions does not exist. With this aim, we study random networks and networks with mesoscale community structure built up from randomly connected cliques. We find that large heterogeneity at the mesoscale level of the network appears to be a sufficient mechanism for the absence of a characteristic time for the dynamics. Such heterogeneity results in dynamical metastable states that survive at any time scale. △ Less

Submitted 27 February, 2009; v1 submitted 25 August, 2008; originally announced August 2008.

Comments: 8 pages, 12 figures

Journal ref: Physical Review E 79, 016109 (2009)

Maximal spanning trees, asset graphs and random matrix denoising in the analysis of dynamics of financial networks

Authors: Tapio Heimo, Kimmo Kaski, Jari Saramaki

Abstract: We study the time dependence of maximal spanning trees and asset graphs based on correlation matrices of stock returns. In these networks the nodes represent companies and links are related to the correlation coefficients between them. Special emphasis is given to the comparison between ordinary and denoised correlation matrices. The analysis of single- and multi-step survival ratios of the corr… ▽ More We study the time dependence of maximal spanning trees and asset graphs based on correlation matrices of stock returns. In these networks the nodes represent companies and links are related to the correlation coefficients between them. Special emphasis is given to the comparison between ordinary and denoised correlation matrices. The analysis of single- and multi-step survival ratios of the corresponding networks reveals that the ordinary correlation matrices are more stable in time than the denoised ones. Our study also shows that some information about the cluster structure of the companies is lost in the denoising procedure. Cluster structure that makes sense from an economic point of view exists, and can easily be observed in networks based on denoised correlation matrices. However, this structure is somewhat clearer in the networks based on ordinary correlation matrices. Some technical aspects, such as the random matrix denoising procedure, are also presented. △ Less

Submitted 19 November, 2008; v1 submitted 28 June, 2008; originally announced June 2008.

Comments: 23 pages, 12 figures, 1 table. v2: 3 references added, minor revisions

Journal ref: Physica A 388, 145 (2009)

A sequential algorithm for fast clique percolation

Authors: Jussi M. Kumpula, Mikko Kivela, Kimmo Kaski, Jari Saramaki

Abstract: In complex network research clique percolation, introduced by Palla et al., is a deterministic community detection method, which allows for overlapping communities and is purely based on local topological properties of a network. Here we present a sequential clique percolation algorithm (SCP) to do fast community detection in weighted and unweighted networks, for cliques of a chosen size. This m… ▽ More In complex network research clique percolation, introduced by Palla et al., is a deterministic community detection method, which allows for overlapping communities and is purely based on local topological properties of a network. Here we present a sequential clique percolation algorithm (SCP) to do fast community detection in weighted and unweighted networks, for cliques of a chosen size. This method is based on sequentially inserting the constituent links to the network and simultaneously keeping track of the emerging community structure. Unlike existing algorithms, the SCP method allows for detecting k-clique communities at multiple weight thresholds in a single run, and can simultaneously produce a dendrogram representation of hierarchical community structure. In sparse weighted networks, the SCP algorithm can also be used for implementing the weighted clique percolation method recently introduced by Farkas et al. The computational time of the SCP algorithm scales linearly with the number of k-cliques in the network. As an example, the method is applied to a product association network, revealing its nested community structure. △ Less

Submitted 30 July, 2008; v1 submitted 10 May, 2008; originally announced May 2008.

Comments: Accepted to Phys. Rev. E, 8 pages, 4 figures

A comparative study of social network models: network evolution models and nodal attribute models

Authors: Riitta Toivonen, Lauri Kovanen, Mikko Kivelä, Jukka-Pekka Onnela, Jari Saramäki, Kimmo Kaski

Abstract: This paper reviews, classifies and compares recent models for social networks that have mainly been published within the physics-oriented complex networks literature. The models fall into two categories: those in which the addition of new links is dependent on the (typically local) network structure (network evolution models, NEMs), and those in which links are generated based only on nodal attr… ▽ More This paper reviews, classifies and compares recent models for social networks that have mainly been published within the physics-oriented complex networks literature. The models fall into two categories: those in which the addition of new links is dependent on the (typically local) network structure (network evolution models, NEMs), and those in which links are generated based only on nodal attributes (nodal attribute models, NAMs). An exponential random graph model (ERGM) with structural dependencies is included for comparison. We fit models from each of these categories to two empirical acquaintance networks with respect to basic network properties. We compare higher order structures in the resulting networks with those in the data, with the aim of determining which models produce the most realistic network structure with respect to degree distributions, assortativity, clustering spectra, geodesic path distributions, and community structure (subgroups with dense internal connections). We find that the nodal attribute models successfully produce assortative networks and very clear community structure. However, they generate unrealistic clustering spectra and peaked degree distributions that do not match empirical data on large social networks. On the other hand, many of the network evolution models produce degree distributions and clustering spectra that agree more closely with data. They also generate assortative networks and community structure, although often not to the same extent as in the data. The ERG model turns out to produce the weakest community structure. △ Less

Submitted 23 December, 2008; v1 submitted 5 May, 2008; originally announced May 2008.

Detecting modules in dense weighted networks with the Potts method

Authors: Tapio Heimo, Jussi Kumpula, Kimmo Kaski, Jari Saramaki

Abstract: We address the problem of multiresolution module detection in dense weighted networks, where the modular structure is encoded in the weights rather than topology. We discuss a weighted version of the q-state Potts method, which was originally introduced by Reichardt and Bornholdt. This weighted method can be directly applied to dense networks. We discuss the dependence of the resolution of the m… ▽ More We address the problem of multiresolution module detection in dense weighted networks, where the modular structure is encoded in the weights rather than topology. We discuss a weighted version of the q-state Potts method, which was originally introduced by Reichardt and Bornholdt. This weighted method can be directly applied to dense networks. We discuss the dependence of the resolution of the method on its tuning parameter and network properties, using sparse and dense weighted networks with built-in modules as example cases. Finally, we apply the method to data on stock price correlations, and show that the resulting modules correspond well to known structural properties of this correlation network. △ Less

Submitted 19 November, 2008; v1 submitted 22 April, 2008; originally announced April 2008.

Comments: 14 pages, 6 figures. v2: 1 figure added, 1 reference added, minor changes. v3: 3 references added, minor changes

Journal ref: Journal of Statistical Mechanics, P08007 (2008)

Spectral methods and cluster structure in correlation-based networks

Authors: Tapio Heimo, Gergely Tibely, Jari Saramaki, Kimmo Kaski, Janos Kertesz

Abstract: We investigate how in complex systems the eigenpairs of the matrices derived from the correlations of multichannel observations reflect the cluster structure of the underlying networks. For this we use daily return data from the NYSE and focus specifically on the spectral properties of weight W_{ij} = |C|_{ij} - δ_{ij} and diffusion matrices D_{ij} = W_{ij}/s_j- δ_{ij}, where C_{ij} is the corre… ▽ More We investigate how in complex systems the eigenpairs of the matrices derived from the correlations of multichannel observations reflect the cluster structure of the underlying networks. For this we use daily return data from the NYSE and focus specifically on the spectral properties of weight W_{ij} = |C|_{ij} - δ_{ij} and diffusion matrices D_{ij} = W_{ij}/s_j- δ_{ij}, where C_{ij} is the correlation matrix and s_i = \sum_j W_{ij} the strength of node j. The eigenvalues (and corresponding eigenvectors) of the weight matrix are ranked in descending order. In accord with the earlier observations the first eigenvector stands for a measure of the market correlations. Its components are to first approximation equal to the strengths of the nodes and there is a second order, roughly linear, correction. The high ranking eigenvectors, excluding the highest ranking one, are usually assigned to market sectors and industrial branches. Our study shows that both for weight and diffusion matrices the eigenpair analysis is not capable of easily deducing the cluster structure of the network without a priori knowledge. In addition we have studied the clustering of stocks using the asset graph approach with and without spectrum based noise filtering. It turns out that asset graphs are quite insensitive to noise and there is no sharp percolation transition as a function of the ratio of bonds included, thus no natural threshold value for that ratio seems to exist. We suggest that these observations can be of use for other correlation based networks as well. △ Less

Submitted 14 August, 2007; originally announced August 2007.

Comments: 26 pages, 14 figures

Journal ref: Physica A 387, 5930 (2008)