Ranking and clustering of nodes in networks with smart teleportation

Assessing spatial structure in marine populations using network theory: A case study of Atlantic sea scallop (Placopecten magellanicus) connectivity

Knowledge of the geographic distribution and connectivity of marine populations is essential for ecological understanding and informing management. Previous works have assessed spatial structure by quantifying exchange using Lagrangian particle-tracking simulations, but their scope of analysis is limited by their use of predefined subpopulations. To instead delineate subpopulations emerging naturally from marine population connectivity, we interpret this connectivity as a network, enabling the use of powerful analytic tools from the field of network theory. The modelling approach presented here uses particle-tracking to construct a transport network, and then applies the community detection algorithm Infomap to identify subpopulations that exhibit high internal connectivity and sparse connectivity with other subpopulations. An established quality metric, the coherence ratio, and a new metric we introduce indicating self-recruitment to subpopulations, dubbed the fortress ratio, are used to interpret community-level exchange. We use the Atlantic sea scallop (Placopecten magellanicus) in the northwest Atlantic as a case study. Results suggest that genetic lineages of P. magellanicus demonstrate spatial substructure that depends on horizontal transport, vertical motility, and suitable habitat. Our results support connectivity previously characterized on Georges Bank and Mid-Atlantic Bight. The Gulf of St. Lawrence genetic lineage is found to consist of five subpopulations that are classified as being a sink, source, permeable, or impermeable using quality metrics. This approach may be applied to other planktonic dispersers and prove useful to management.

Single-trajectory map equation

Community detection, the process of identifying module structures in complex systems represented on networks, is an effective tool in various fields of science. The map equation, which is an information-theoretic framework based on the random walk on a network, is a particularly popular community detection method. Despite its outstanding performance in many applications, the inner workings of the map equation have not been thoroughly studied. Herein, we revisit the original formulation of the map equation and address the existence of its "raw form," which we refer to as the single-trajectory map equation. This raw form sheds light on many details behind the principle of the map equation that are hidden in the steady-state limit of the random walk. Most importantly, the single-trajectory map equation provides a more balanced community structure, naturally reducing the tendency of the overfitting phenomenon in the map equation.

Network location and clustering of genetic mutations determine chronicity in a stylized model of genetic diseases

In a highly simplified view, a disease can be seen as the phenotype emerging from the interplay of genetic predisposition and fluctuating environmental stimuli. We formalize this situation in a minimal model, where a network (representing cellular regulation) serves as an interface between an input layer (representing environment) and an output layer (representing functional phenotype). Genetic predisposition for a disease is represented as a loss of function of some network nodes. Reduced, but non-zero, output indicates disease. The simplicity of this genetic disease model and its deep relationship to percolation theory allows us to understand the interplay between disease, network topology and the location and clusters of affected network nodes. We find that our model generates two different characteristics of diseases, which can be interpreted as chronic and acute diseases. In its stylized form, our model provides a new view on the relationship between genetic mutations and the type and severity of a disease.

Mapping the scientific structure and evolution of renewable energy for sustainable development

The integration of renewable energy and sustainable development (RE&SD) can help overcome existing obstacles and create opportunities for renewable energy deployment to achieve sustainable development goals. In view of the limited research on science mapping and visualization analyses of RE&SD, this study sought to determine the scientific structure and evolution based on longitudinal and mapping change analysis. As an entity in the knowledge base, keyword and subject were considered essential information of documents. The co-word network was generated using SciMAT to reveal the dynamic aspects of the scientific research in the five subperiods. The thematic evolutionary analysis identified two main RE&SD thematic areas, with the current research hotspots that involved technological, environmental, sustainable energy innovation, and sustainable biofuel contributions. The alluvial diagram using MapEquation revealed significant structural changes from subject data. Clusters of subjects continued to grow, and more interdisciplinary integration was undergoing. This study provides a systematic study of RE&SD research, and the future research of RE&SD may inevitably consider renewable energy investment and renewable energy perspective approaches to achieve sustainable development goals.

Network-medicine framework for studying disease trajectories in U.S. veterans

A better understanding of the sequential and temporal aspects in which diseases occur in patient's lives is essential for developing improved intervention strategies that reduce burden and increase the quality of health services. Here we present a network-based framework to study disease relationships using Electronic Health Records from > 9 million patients in the United States Veterans Health Administration (VHA) system. We create the Temporal Disease Network, which maps the sequential aspects of disease co-occurrence among patients and demonstrate that network properties reflect clinical aspects of the respective diseases. We use the Temporal Disease Network to identify disease groups that reflect patterns of disease co-occurrence and the flow of patients among diagnoses. Finally, we define a strategy for the identification of trajectories that lead from one disease to another. The framework presented here has the potential to offer new insights for disease treatment and prevention in large health care systems.

Regional economic integration via detection of circular flow in international value-added network

Global value chains are formed through value-added trade, and some regions promote economic integration by concluding regional trade agreements to promote these chains. However, it has not been established to quantitatively assess the scope and extent of economic integration involving various sectors in multiple countries. In this study, we used the World Input-Output Database to create a cross-border sector-wise network of trade in value-added (international value-added network) covering the period of 2000-2014 and evaluated them using network science methods. By applying Infomap to the international value-added network, we confirmed two regional communities: Europe and the Pacific Rim. We applied Helmholtz-Hodge decomposition to the value-added flows within the region into potential and circular flows, and clarified the annual evolution of the potential and circular relationships between countries and sectors. The circular flow component of the decomposition was used to define an economic integration index. Findings confirmed that the degree of economic integration in Europe declined sharply after the economic crisis in 2009 to a level lower than that in the Pacific Rim. The European economic integration index recovered in 2011 but again fell below that of the Pacific Rim in 2013. Moreover, sectoral economic integration indices suggest what Europe depends on Russia in natural resources makes the European economic integration index unstable. On the other hand, the indices of the Pacific Rim suggest the steady economic integration index of the Pacific Rim captures the stable global value chains from natural resources to construction and manufactures of motor vehicles and high-tech products.

Bibliometric and Visualized Analysis of China's Smart Grid Research 2008-2018

Smart grid (SG) offers great advantages in renewable energy integration and has become a popular trend of modern power development recently; meanwhile China is the second most prolific country using SG. Hence the purpose of this study is to get access to the research status, development, and trends of SG in China based on the 3,558 published papers obtained from the WOS core library and application of the bibliometric method and visualization analysis software VOSviewer and alluvial diagrams. The results consequently demonstrate some valuable insights. Firstly, the volume of publications in China's SG is on the rise, and the cooperation between countries and institutions is getting closer. Besides, the research hotspots have obvious interdisciplinary characteristics. Taking into consideration the impact of the information and communication field on SG, the major current research hotspots include wireless sensor network (WSN), internet of things (IoT), smart meter, big data, and security. Taking into consideration the impact of SG on traditional power systems, the main hotspots cover demand response, micro-grid, distributed generation, and electric vehicle (EV). Furthermore, China's SG research shows a trend from a single theme to diversified development. The research themes during 2010–2018 have deepened with most studies focusing on the traditional power system. The findings of this paper provide some enlightenment on China's SG research, which can present scholars with an overview of the macro perspective, help them understand the latest development of the SG field in China and offer useful guidance for future research in this subject as well.

Generalized Markov stability of network communities

We address the problem of community detection in networks by introducing a general definition of Markov stability, based on the difference between the probability fluxes of a Markov chain on the network at different timescales. The specific implementation of the quality function and the resulting optimal community structure thus become dependent both on the type of Markov process and on the specific Markov times considered. For instance, if we use a natural Markov chain dynamics and discount its stationary distribution (that is, we take as reference process the dynamics at infinite time) we obtain the standard formulation of the Markov stability. Notably, the possibility to use finite-time transition probabilities to define the reference process naturally allows detecting communities at different resolutions, without the need to consider a continuous-time Markov chain in the small time limit. The main advantage of our general formulation of Markov stability based on dynamical flows is that we work with lumped Markov chains on network partitions, having the same stationary distribution of the original process. In this way the form of the quality function becomes invariant under partitioning, leading to a self-consistent definition of community structures at different aggregation scales.

Map equation with metadata: Varying the role of attributes in community detection

Much of the community detection literature studies structural communities, communities defined solely by the connectivity patterns of the network. Often networks contain additional metadata which can inform community detection such as the grade and gender of students in a high school social network. In this work, we introduce a tuning parameter to the content map equation that allows users of the Infomap community detection algorithm to control the metadata's relative importance for identifying network structure. On synthetic networks, we show that our algorithm can overcome the structural detectability limit when the metadata are well aligned with community structure. On real-world networks, we show how our algorithm can achieve greater mutual information with the metadata at a cost in the traditional map equation. Our tuning parameter, like the focusing knob of a microscope, allows users to "zoom in" and "zoom out" on communities with varying levels of focus on the metadata.

Multiscale dynamical embeddings of complex networks

Complex systems and relational data are often abstracted as dynamical processes on networks. To understand, predict, and control their behavior, a crucial step is to extract reduced descriptions of such networks. Inspired by notions from control theory, we propose a time-dependent dynamical similarity measure between nodes, which quantifies the effect a node-input has on the network. This dynamical similarity induces an embedding that can be employed for several analysis tasks. Here we focus on (i) dimensionality reduction, i.e., projecting nodes onto a low-dimensional space that captures dynamic similarity at different timescales, and (ii) how to exploit our embeddings to uncover functional modules. We exemplify our ideas through case studies focusing on directed networks without strong connectivity and signed networks. We further highlight how certain ideas from community detection can be generalized and linked to control theory, by using the here developed dynamical perspective.

Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap

Comprehending complex systems by simplifying and highlighting important dynamical patterns requires modeling and mapping higher-order network flows. However, complex systems come in many forms and demand a range of representations, including memory and multilayer networks, which in turn call for versatile community-detection algorithms to reveal important modular regularities in the flows. Here we show that various forms of higher-order network flows can be represented in a unified way with networks that distinguish physical nodes for representing a complex system’s objects from state nodes for describing flows between the objects. Moreover, these so-called sparse memory networks allow the information-theoretic community detection method known as the map equation to identify overlapping and nested flow modules in data from a range of different higher-order interactions such as multistep, multi-source, and temporal data. We derive the map equation applied to sparse memory networks and describe its search algorithm Infomap, which can exploit the flexibility of sparse memory networks. Together they provide a general solution to reveal overlapping modular patterns in higher-order flows through complex systems.

Assessing larval connectivity for marine spatial planning in the Adriatic

There are plans to start building offshore marine renewable energy devices throughout the Mediterranean and the Adriatic has been identified as a key location for wind farm developments. The development of offshore wind farms in the area would provide hard substrata for the settlement of sessile benthos. Since the seafloor of the Adriatic is predominantly sedimentary this may alter the larval connectivity of benthic populations in the region. Here, we simulated the release of larvae from benthic populations along the coasts of the Adriatic Sea using coupled bio-physical models and investigated the effect of pelagic larval duration on dispersal. Our model simulations show that currents typically carry particles from east to west across the Adriatic, whereas particles released along western coasts tend to remain there with the Puglia coast of Italy acting as a sink for larvae from benthic populations. We identify areas of high connectivity, as well as areas that are much more isolated, and discuss how these results can be used to inform marine spatial planning and the licensing of offshore marine renewable energy developments.

EIGENVECTOR-BASED CENTRALITY MEASURES FOR TEMPORAL NETWORKS. MULTISCALE MODELING & SIMULATION : A SIAM INTERDISCIPLINARY JOURNAL 2017;15:537-574. [PMID: 29046619 PMCID: PMC5643020 DOI: 10.1137/16m1066142]

Numerous centrality measures have been developed to quantify the importances of nodes in time-independent networks, and many of them can be expressed as the leading eigenvector of some matrix. With the increasing availability of network data that changes in time, it is important to extend such eigenvector-based centrality measures to time-dependent networks. In this paper, we introduce a principled generalization of network centrality measures that is valid for any eigenvector-based centrality. We consider a temporal network with N nodes as a sequence of T layers that describe the network during different time windows, and we couple centrality matrices for the layers into a supra-centrality matrix of size NT × NT whose dominant eigenvector gives the centrality of each node i at each time t. We refer to this eigenvector and its components as a joint centrality, as it reflects the importances of both the node i and the time layer t. We also introduce the concepts of marginal and conditional centralities, which facilitate the study of centrality trajectories over time. We find that the strength of coupling between layers is important for determining multiscale properties of centrality, such as localization phenomena and the time scale of centrality changes. In the strong-coupling regime, we derive expressions for time-averaged centralities, which are given by the zeroth-order terms of a singular perturbation expansion. We also study first-order terms to obtain first-order-mover scores, which concisely describe the magnitude of nodes' centrality changes over time. As examples, we apply our method to three empirical temporal networks: the United States Ph.D. exchange in mathematics, costarring relationships among top-billed actors during the Golden Age of Hollywood, and citations of decisions from the United States Supreme Court.

Community detection in weighted brain connectivity networks beyond the resolution limit

Graph theory provides a powerful framework to investigate brain functional connectivity networks and their modular organization. However, most graph-based methods suffer from a fundamental resolution limit that may have affected previous studies and prevented detection of modules, or "communities", that are smaller than a specific scale. Surprise, a resolution-limit-free function rooted in discrete probability theory, has been recently introduced and applied to brain networks, revealing a wide size-distribution of functional modules (Nicolini and Bifone, 2016), in contrast with many previous reports. However, the use of Surprise is limited to binary networks, while brain networks are intrinsically weighted, reflecting a continuous distribution of connectivity strengths between different brain regions. Here, we propose Asymptotical Surprise, a continuous version of Surprise, for the study of weighted brain connectivity networks, and validate this approach in synthetic networks endowed with a ground-truth modular structure. We compare Asymptotical Surprise with leading community detection methods currently in use and show its superior sensitivity in the detection of small modules even in the presence of noise and intersubject variability such as those observed in fMRI data. We apply our novel approach to functional connectivity networks from resting state fMRI experiments, and demonstrate a heterogeneous modular organization, with a wide distribution of clusters spanning multiple scales. Finally, we discuss the implications of these findings for the identification of connector hubs, the brain regions responsible for the integration of the different network elements, showing that the improved resolution afforded by Asymptotical Surprise leads to a different classification compared to current methods.

•

Methods to study modularity of brain connectivity networks have a resolution limit.

•

Asymptotical Surprise, a nearly resolution-limit-free method for weighted graphs, is proposed.

•

Improved sensitivity and specificity are demonstrated in model networks.

•

Resting state functional connectivity networks consist of heterogeneous modules.

•

Classification of hubs in function connectivity networks should be revised.

Network Analysis and Visualization of Mouse Retina Connectivity Data

The largest available cellular level connectivity map, of a 0.1 mm sample of the mouse retina Inner Plexiform Layer, was analysed using network models and visualized using spectral graph layouts and observed cell coordinates. This allows key nodes in the network to be identified with retinal neurons. Their strongest synaptic links can trace pathways in the network, elucidating possible circuits. Modular decomposition of the network, by sampling signal flows over nodes and links using the InfoMap method, shows discrete modules of cone bipolar cells that form a tiled mosaic in the retinal plane. The highest flow nodes, calculated by InfoMap, proved to be the most useful landmarks for elucidating possible circuits. Their dominant links to high flow amacrine cells reveal possible circuits linking bipolar through to ganglion cells and show an Off-On discrimination between the Left-Right sections of the sample. Circuits suggested by this analysis confirm known roles for some cells and point to roles for others.

Using higher-order Markov models to reveal flow-based communities in networks

Complex systems made of interacting elements are commonly abstracted as networks, in which nodes are associated with dynamic state variables, whose evolution is driven by interactions mediated by the edges. Markov processes have been the prevailing paradigm to model such a network-based dynamics, for instance in the form of random walks or other types of diffusions. Despite the success of this modelling perspective for numerous applications, it represents an over-simplification of several real-world systems. Importantly, simple Markov models lack memory in their dynamics, an assumption often not realistic in practice. Here, we explore possibilities to enrich the system description by means of second-order Markov models, exploiting empirical pathway information. We focus on the problem of community detection and show that standard network algorithms can be generalized in order to extract novel temporal information about the system under investigation. We also apply our methodology to temporal networks, where we can uncover communities shaped by the temporal correlations in the system. Finally, we discuss relations of the framework of second order Markov processes and the recently proposed formalism of using non-backtracking matrices for community detection.

Interest communities and flow roles in directed networks: the Twitter network of the UK riots

Directionality is a crucial ingredient in many complex networks in which information, energy or influence are transmitted. In such directed networks, analysing flows (and not only the strength of connections) is crucial to reveal important features of the network that might go undetected if the orientation of connections is ignored. We showcase here a flow-based approach for community detection through the study of the network of the most influential Twitter users during the 2011 riots in England. Firstly, we use directed Markov Stability to extract descriptions of the network at different levels of coarseness in terms of interest communities, i.e. groups of nodes within which flows of information are contained and reinforced. Such interest communities reveal user groupings according to location, profession, employer and topic. The study of flows also allows us to generate an interest distance, which affords a personalized view of the attention in the network as viewed from the vantage point of any given user. Secondly, we analyse the profiles of incoming and outgoing long-range flows with a combined approach of role-based similarity and the novel relaxed minimum spanning tree algorithm to reveal that the users in the network can be classified into five roles. These flow roles go beyond the standard leader/follower dichotomy and differ from classifications based on regular/structural equivalence. We then show that the interest communities fall into distinct informational organigrams characterized by a different mix of user roles reflecting the quality of dialogue within them. Our generic framework can be used to provide insight into how flows are generated, distributed, preserved and consumed in directed networks.

Community Detection in Signed Networks: the Role of Negative ties in Different Scales

Extracting community structure of complex network systems has many applications from engineering to biology and social sciences. There exist many algorithms to discover community structure of networks. However, it has been significantly under-explored for networks with positive and negative links as compared to unsigned ones. Trying to fill this gap, we measured the quality of partitions by introducing a Map Equation for signed networks. It is based on the assumption that negative relations weaken positive flow from a node towards a community, and thus, external (internal) negative ties increase the probability of staying inside (escaping from) a community. We further extended the Constant Potts Model, providing a map spectrum for signed networks. Accordingly, a partition is selected through balancing between abridgment and expatiation of a signed network. Most importantly, multi-scale spectrum of signed networks revealed how informative are negative ties in different scales, and quantified the topological placement of negative ties between dense positive ones. Moreover, an inconsistency was found in the signed Modularity: as the number of negative ties increases, the density of positive ties is neglected more. These results shed lights on the community structure of signed networks.

Think locally, act locally: detection of small, medium-sized, and large communities in large networks

It is common in the study of networks to investigate intermediate-sized (or "meso-scale") features to try to gain an understanding of network structure and function. For example, numerous algorithms have been developed to try to identify "communities," which are typically construed as sets of nodes with denser connections internally than with the remainder of a network. In this paper, we adopt a complementary perspective that communities are associated with bottlenecks of locally biased dynamical processes that begin at seed sets of nodes, and we employ several different community-identification procedures (using diffusion-based and geodesic-based dynamics) to investigate community quality as a function of community size. Using several empirical and synthetic networks, we identify several distinct scenarios for "size-resolved community structure" that can arise in real (and realistic) networks: (1) the best small groups of nodes can be better than the best large groups (for a given formulation of the idea of a good community); (2) the best small groups can have a quality that is comparable to the best medium-sized and large groups; and (3) the best small groups of nodes can be worse than the best large groups. As we discuss in detail, which of these three cases holds for a given network can make an enormous difference when investigating and making claims about network community structure, and it is important to take this into account to obtain reliable downstream conclusions. Depending on which scenario holds, one may or may not be able to successfully identify "good" communities in a given network (and good communities might not even exist for a given community quality measure), the manner in which different small communities fit together to form meso-scale network structures can be very different, and processes such as viral propagation and information diffusion can exhibit very different dynamics. In addition, our results suggest that, for many large realistic networks, the output of locally biased methods that focus on communities that are centered around a given seed node (or set of seed nodes) might have better conceptual grounding and greater practical utility than the output of global community-detection methods. They also illustrate structural properties that are important to consider in the development of better benchmark networks to test methods for community detection.

Estimating the resolution limit of the map equation in community detection

A community detection algorithm is considered to have a resolution limit if the scale of the smallest modules that can be resolved depends on the size of the analyzed subnetwork. The resolution limit is known to prevent some community detection algorithms from accurately identifying the modular structure of a network. In fact, any global objective function for measuring the quality of a two-level assignment of nodes into modules must have some sort of resolution limit or an external resolution parameter. However, it is yet unknown how the resolution limit affects the so-called map equation, which is known to be an efficient objective function for community detection. We derive an analytical estimate and conclude that the resolution limit of the map equation is set by the total number of links between modules instead of the total number of links in the full network as for modularity. This mechanism makes the resolution limit much less restrictive for the map equation than for modularity; in practice, it is orders of magnitudes smaller. Furthermore, we argue that the effect of the resolution limit often results from shoehorning multilevel modular structures into two-level descriptions. As we show, the hierarchical map equation effectively eliminates the resolution limit for networks with nested multilevel modular structures.

Time development in the early history of social networks: link stabilization, group dynamics, and segregation

Studies of the time development of empirical networks usually investigate late stages where lasting connections have already stabilized. Empirical data on early network history are rare but needed for a better understanding of how social network topology develops in real life. Studying students who are beginning their studies at a university with no or few prior connections to each other offers a unique opportunity to investigate the formation and early development of link patterns and community structure in social networks. During a nine week introductory physics course, first year physics students were asked to identify those with whom they communicated about problem solving in physics during the preceding week. We use these students' self reports to produce time dependent student interaction networks. We investigate these networks to elucidate possible effects of different student attributes in early network formation. Changes in the weekly number of links show that while roughly half of all links change from week to week, students also reestablish a growing number of links as they progress through their first weeks of study. Using the Infomap community detection algorithm, we show that the networks exhibit community structure, and we use non-network student attributes, such as gender and end-of-course grade to characterize communities during their formation. Specifically, we develop a segregation measure and show that students structure themselves according to gender and pre-organized sections (in which students engage in problem solving and laboratory work), but not according to end-of-coure grade. Alluvial diagrams of consecutive weeks' communities show that while student movement between groups are erratic in the beginnning of their studies, they stabilize somewhat towards the end of the course. Taken together, the analyses imply that student interaction networks stabilize quickly and that students establish collaborations based on who is immediately available to them and on observable personal characteristics.

Revealing cell assemblies at multiple levels of granularity

BACKGROUND

Current neuronal monitoring techniques, such as calcium imaging and multi-electrode arrays, enable recordings of spiking activity from hundreds of neurons simultaneously. Of primary importance in systems neuroscience is the identification of cell assemblies: groups of neurons that cooperate in some form within the recorded population.

NEW METHOD

We introduce a simple, integrated framework for the detection of cell-assemblies from spiking data without a priori assumptions about the size or number of groups present. We define a biophysically-inspired measure to extract a directed functional connectivity matrix between both excitatory and inhibitory neurons based on their spiking history. The resulting network representation is analyzed using the Markov Stability framework, a graph theoretical method for community detection across scales, to reveal groups of neurons that are significantly related in the recorded time-series at different levels of granularity.

RESULTS AND COMPARISON WITH EXISTING METHODS

Using synthetic spike-trains, including simulated data from leaky-integrate-and-fire networks, our method is able to identify important patterns in the data such as hierarchical structure that are missed by other standard methods. We further apply the method to experimental data from retinal ganglion cells of mouse and salamander, in which we identify cell-groups that correspond to known functional types, and to hippocampal recordings from rats exploring a linear track, where we detect place cells with high fidelity.

CONCLUSIONS

We present a versatile method to detect neural assemblies in spiking data applicable across a spectrum of relevant scales that contributes to understanding spatio-temporal information gathered from systems neuroscience experiments.

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

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

Flow motifs reveal limitations of the static framework to represent human interactions

Networks are commonly used to define underlying interaction structures where infections, information, or other quantities may spread. Although the standard approach has been to aggregate all links into a static structure, some studies have shown that the time order in which the links are established may alter the dynamics of spreading. In this paper, we study the impact of the time ordering in the limits of flow on various empirical temporal networks. By using a random walk dynamics, we estimate the flow on links and convert the original undirected network (temporal and static) into a directed flow network. We then introduce the concept of flow motifs and quantify the divergence in the representativity of motifs when using the temporal and static frameworks. We find that the regularity of contacts and persistence of vertices (common in email communication and face-to-face interactions) result on little differences in the limits of flow for both frameworks. On the other hand, in the case of communication within a dating site and of a sexual network, the flow between vertices changes significantly in the temporal framework such that the static approximation poorly represents the structure of contacts. We have also observed that cliques with 3 and 4 vertices containing only low-flow links are more represented than the same cliques with all high-flow links. The representativity of these low-flow cliques is higher in the temporal framework. Our results suggest that the flow between vertices connected in cliques depend on the topological context in which they are placed and in the time sequence in which the links are established. The structure of the clique alone does not completely characterize the potential of flow between the vertices.

Encoding dynamics for multiscale community detection: Markov time sweeping for the map equation

The detection of community structure in networks is intimately related to finding a concise description of the network in terms of its modules. This notion has been recently exploited by the map equation formalism [Rosvall and Bergstrom, Proc. Natl. Acad. Sci. USA 105, 1118 (2008)] through an information-theoretic description of the process of coding inter- and intracommunity transitions of a random walker in the network at stationarity. However, a thorough study of the relationship between the full Markov dynamics and the coding mechanism is still lacking. We show here that the original map coding scheme, which is both block-averaged and one-step, neglects the internal structure of the communities and introduces an upper scale, the "field-of-view" limit, in the communities it can detect. As a consequence, map is well tuned to detect clique-like communities but can lead to undesirable overpartitioning when communities are far from clique-like. We show that a signature of this behavior is a large compression gap: The map description length is far from its ideal limit. To address this issue, we propose a simple dynamic approach that introduces time explicitly into the map coding through the analysis of the weighted adjacency matrix of the time-dependent multistep transition matrix of the Markov process. The resulting Markov time sweeping induces a dynamical zooming across scales that can reveal (potentially multiscale) community structure above the field-of-view limit, with the relevant partitions indicated by a small compression gap.