Map equation for link communities

Overlapping community detection in networks based on link partitioning and partitioning around medoids

In this paper, we present a new method for detecting overlapping communities in networks with a predefined number of clusters called LPAM (Link Partitioning Around Medoids). The overlapping communities in the graph are obtained by detecting the disjoint communities in the associated line graph employing link partitioning and partitioning around medoids which are done through the use of a distance function defined on the set of nodes. We consider both the commute distance and amplified commute distance as distance functions. The performance of the LPAM method is evaluated with computational experiments on real life instances, as well as synthetic network benchmarks. For small and medium-size networks, the exact solution was found, while for large networks we found solutions with a heuristic version of the LPAM method.

Dynamic Analyses of Contagion Risk and Module Evolution on the SSE A-Shares Market Based on Minimum Information Entropy

The interactive effect is significant in the Chinese stock market, exacerbating the abnormal market volatilities and risk contagion. Based on daily stock returns in the Shanghai Stock Exchange (SSE) A-shares, this paper divides the period between 2005 and 2018 into eight bull and bear market stages to investigate interactive patterns in the Chinese financial market. We employ the Least Absolute Shrinkage and Selection Operator (LASSO) method to construct the stock network, compare the heterogeneity of bull and bear markets, and further use the Map Equation method to analyse the evolution of modules in the SSE A-shares market. Empirical results show that (1) the connected effect is more significant in bear markets than bull markets and gives rise to abnormal volatilities in the stock market; (2) a system module can be found in the network during the first four stages, and the industry aggregation effect leads to module differentiation in the last four stages; (3) some stocks have leading effects on others throughout eight periods, and medium- and small-cap stocks with poor financial conditions are more likely to become risk sources, especially in bear markets. Our conclusions are beneficial to improving investment strategies and making regulatory policies.

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.

A Central Edge Selection Based Overlapping Community Detection Algorithm for the Detection of Overlapping Structures in Protein⁻Protein Interaction Networks

Overlapping structures of protein⁻protein interaction networks are very prevalent in different biological processes, which reflect the sharing mechanism to common functional components. The overlapping community detection (OCD) algorithm based on central node selection (CNS) is a traditional and acceptable algorithm for OCD in networks. The main content of CNS is the central node selection and the clustering procedure. However, the original CNS does not consider the influence among the nodes and the importance of the division of the edges in networks. In this paper, an OCD algorithm based on a central edge selection (CES) algorithm for detection of overlapping communities of protein⁻protein interaction (PPI) networks is proposed. Different from the traditional CNS algorithms for OCD, the proposed algorithm uses community magnetic interference (CMI) to obtain more reasonable central edges in the process of CES, and employs a new distance between the non-central edge and the set of the central edges to divide the non-central edge into the correct cluster during the clustering procedure. In addition, the proposed CES improves the strategy of overlapping nodes pruning (ONP) to make the division more precisely. The experimental results on three benchmark networks and three biological PPI networks of Mus. musculus, Escherichia coli, and Cerevisiae show that the CES algorithm performs well.

Micro-blog user community discovery using generalized SimRank edge weighting method

Community discovery is one of the most popular issues in analyzing and understanding a network. Previous research suggests that the discovery can be enhanced by assigning weights to the edges of the network. This paper proposes a novel edge weighting method, which balances both local and global weighting based on the idea of shared neighbor ranging between users and the interpersonal significance of the social network community. We assume that users belonging to the same community have similar relationship network structures. By controlling the measure of "neighborhood", this method can adequately adapt to real-world networks. Therefore, the famous similarity calculation method-SimRank-can be regarded as a special case of our method. According to the practical significance of social networks, we propose a new evaluation method that uses the communication rate to measure its divided demerit to better express users' interaction relations than the ordinary modularity Q. Furthermore, the fast Newman algorithm is extended to weighted networks. In addition, we use four real networks in the largest Chinese micro-blog website Sina. The results of experiments demonstrate that the proposed method easily meets the balancing requirements and is more robust to different kinds of networks. The experimental results also indicate that the proposed algorithm outperforms several conventional weighting methods.

Inverse Resolution Limit of Partition Density and Detecting Overlapping Communities by Link-Surprise

Finding overlapping communities of complex networks remains a challenge in network science. To address this challenge, one of the widely used approaches is finding the communities of links by optimizing the objective function, partition density. In this study, we show that partition density suffers from inverse resolution limit; it has a strong preference to triangles. This resolution limit makes partition density an improper objective function for global optimization. The conditions where partition density prefers triangles to larger link community structures are analytically derived and confirmed with global optimization calculations using synthetic and real-world networks. To overcome this limitation of partition density, we suggest an alternative measure, Link Surprise, to find link communities, which is suitable for global optimization. Benchmark studies demonstrate that global optimization of Link Surprise yields meaningful and more accurate link community structures than partition density optimization.

Discovering communities in complex networks by edge label propagation

The discovery of the community structure of real-world networks is still an open problem. Many methods have been proposed to shed light on this problem, and most of these have focused on discovering node community. However, link community is also a powerful framework for discovering overlapping communities. Here we present a novel edge label propagation algorithm (ELPA), which combines the natural advantage of link communities with the efficiency of the label propagation algorithm (LPA). ELPA can discover both link communities and node communities. We evaluated ELPA on both synthetic and real-world networks, and compared it with five state-of-the-art methods. The results demonstrate that ELPA performs competitively with other algorithms.

An edge-centric perspective on the human connectome: link communities in the brain

Brain function depends on efficient processing and integration of information within a complex network of neural interactions, known as the connectome. An important aspect of connectome architecture is the existence of community structure, providing an anatomical basis for the occurrence of functional specialization. Typically, communities are defined as groups of densely connected network nodes, representing clusters of brain regions. Looking at the connectome from a different perspective, instead focusing on the interconnecting links or edges, we find that the white matter pathways between brain regions also exhibit community structure. Eleven link communities were identified: five spanning through the midline fissure, three through the left hemisphere and three through the right hemisphere. We show that these link communities are consistently identifiable and investigate the network characteristics of their underlying white matter pathways. Furthermore, examination of the relationship between link communities and brain regions revealed that the majority of brain regions participate in multiple link communities. In particular, the highly connected and central hub regions showed a rich level of community participation, supporting the notion that these hubs play a pivotal role as confluence zones in which neural information from different domains merges.

Identification of hybrid node and link communities in complex networks

Identifying communities in complex networks is an effective means for analyzing complex systems, with applications in diverse areas such as social science, engineering, biology and medicine. Finding communities of nodes and finding communities of links are two popular schemes for network analysis. These schemes, however, have inherent drawbacks and are inadequate to capture complex organizational structures in real networks. We introduce a new scheme and an effective approach for identifying complex mixture structures of node and link communities, called hybrid node-link communities. A central piece of our approach is a probabilistic model that accommodates node, link and hybrid node-link communities. Our extensive experiments on various real-world networks, including a large protein-protein interaction network and a large network of semantically associated words, illustrated that the scheme for hybrid communities is superior in revealing network characteristics. Moreover, the new approach outperformed the existing methods for finding node or link communities separately.

Combined node and link partitions method for finding overlapping communities in complex networks

Community detection in complex networks is a fundamental data analysis task in various domains, and how to effectively find overlapping communities in real applications is still a challenge. In this work, we propose a new unified model and method for finding the best overlapping communities on the basis of the associated node and link partitions derived from the same framework. Specifically, we first describe a unified model that accommodates node and link communities (partitions) together, and then present a nonnegative matrix factorization method to learn the parameters of the model. Thereafter, we infer the overlapping communities based on the derived node and link communities, i.e., determine each overlapped community between the corresponding node and link community with a greedy optimization of a local community function conductance. Finally, we introduce a model selection method based on consensus clustering to determine the number of communities. We have evaluated our method on both synthetic and real-world networks with ground-truths, and compared it with seven state-of-the-art methods. The experimental results demonstrate the superior performance of our method over the competing ones in detecting overlapping communities for all analysed data sets. Improved performance is particularly pronounced in cases of more complicated networked community structures.

Mobile recommendation based on link community detection

Since traditional mobile recommendation systems have difficulty in acquiring complete and accurate user information in mobile networks, the accuracy of recommendation is not high. In order to solve this problem, this paper proposes a novel mobile recommendation algorithm based on link community detection (MRLD). MRLD executes link label diffusion algorithm and maximal extended modularity (EQ) of greedy search to obtain the link community structure, and overlapping nodes belonging analysis (ONBA) is adopted to adjust the overlapping nodes in order to get the more accurate community structure. MRLD is tested on both synthetic and real-world networks, and the experimental results show that our approach is valid and feasible.

Link community detection using generative model and nonnegative matrix factorization

Discovery of communities in complex networks is a fundamental data analysis problem with applications in various domains. While most of the existing approaches have focused on discovering communities of nodes, recent studies have shown the advantages and uses of link community discovery in networks. Generative models provide a promising class of techniques for the identification of modular structures in networks, but most generative models mainly focus on the detection of node communities rather than link communities. In this work, we propose a generative model, which is based on the importance of each node when forming links in each community, to describe the structure of link communities. We proceed to fit the model parameters by taking it as an optimization problem, and solve it using nonnegative matrix factorization. Thereafter, in order to automatically determine the number of communities, we extend the above method by introducing a strategy of iterative bipartition. This extended method not only finds the number of communities all by itself, but also obtains high efficiency, and thus it is more suitable to deal with large and unexplored real networks. We test this approach on both synthetic benchmarks and real-world networks including an application on a large biological network, and compare it with two highly related methods. Results demonstrate the superior performance of our approach over competing methods for the detection of link communities.

Identifying overlapping and hierarchical thematic structures in networks of scholarly papers: a comparison of three approaches

The aim of this paper is to introduce and assess three algorithms for the identification of overlapping thematic structures in networks of papers. We implemented three recently proposed approaches to the identification of overlapping and hierarchical substructures in graphs and applied the corresponding algorithms to a network of 492 information-science papers coupled via their cited sources. The thematic substructures obtained and overlaps produced by the three hierarchical cluster algorithms were compared to a content-based categorisation, which we based on the interpretation of titles, abstracts, and keywords. We defined sets of papers dealing with three topics located on different levels of aggregation: h-index, webometrics, and bibliometrics. We identified these topics with branches in the dendrograms produced by the three cluster algorithms and compared the overlapping topics they detected with one another and with the three predefined paper sets. We discuss the advantages and drawbacks of applying the three approaches to paper networks in research fields.