Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks

Temporal networks are widely used models for describing the architecture of complex systems. Network memory -- that is the dependence of a temporal network's structure on its past -- has been shown to play a prominent role in diffusion, epidemics and other processes occurring over the network, and even to alter its community structure. Recent works have proposed to estimate the length of memory in a temporal network by using high-order Markov models. Here we show that network...

Community structure is a critical feature of real networks, providing insights into nodes' internal organization. Nowadays, with the availability of highly detailed temporal networks such as link streams, studying community structures becomes more complex due to increased data precision and time sensitivity. Despite numerous algorithms developed in the past decade for dynamic community discovery, assessing their performance on link streams remains a challenge. Synthetic bench...

Identifying community structure of a complex network provides insight to the interdependence between the network topology and emergent collective behaviors of networks, while detecting such invariant communities in a time-varying network is more challenging. In this paper, we define the temporal stable community and newly propose the concept of dynamic modularity to evaluate the stable community structures in time-varying networks, which is robust against small changes as ver...

Detecting community structures in social networks has gained considerable attention in recent years. However, lack of prior knowledge about the number of communities, and their overlapping nature have made community detection a challenging problem. Moreover, many of the existing methods only consider static networks, while most of real world networks are dynamic and evolve over time. Hence, finding consistent overlapping communities in dynamic networks without any prior knowl...

In this paper a simple but efficient real-time detecting algorithm is proposed for tracking community structure of dynamic networks. Community structure is intuitively characterized as divisions of network nodes into subgroups, within which nodes are densely connected while between which they are sparsely connected. To evaluate the quality of community structure of a network, a metric called modularity is proposed and many algorithms are developed on optimizing it. However, m...

There are fundamental differences between citation networks and other classes of graphs. In particular, given that citation networks are directed and acyclic, methods developed primarily for use with undirected social network data may face obstacles. This is particularly true for the dynamic development of community structure in citation networks. Namely, it is neither clear when it is appropriate to employ existing community detection approaches nor is it clear how to choose...

Social relationships can be divided into different classes based on the regularity with which they occur and the similarity among them. Thus, rare and somewhat similar relationships are random and cause noise in a social network, thus hiding the actual structure of the network and preventing an accurate analysis of it. In this context, in this paper we propose a process to handle social network data that exploits temporal features to improve the detection of communities by ex...

Recent years have seen a surge of interest in the analysis of complex networks, facilitated by the availability of relational data and the increasingly powerful computational resources that can be employed for their analysis. Naturally, the study of real-world systems leads to highly complex networks and a current challenge is to extract intelligible, simplified descriptions from the network in terms of relevant subgraphs, which can provide insight into the structure and func...

Network representations have been effectively employed to analyze complex systems across various areas and applications, leading to the development of network science as a core tool to study systems with multiple components and complex interactions. There is a growing interest in understanding the temporal dynamics of complex networks to decode the underlying dynamic processes through the temporal changes in network structure. Community detection algorithms, which are special...

The description of large temporal graphs requires effective methods giving an appropriate mesoscopic partition. Many approaches exist today to detect communities in static graphs. However, many networks are intrinsically dynamical, and need a dynamic mesoscale description, as interpreting them as static networks would cause loss of important information. For example, dynamic processes such as the emergence of new scientific disciplines, their fusion, split or death need a mes...