Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA new method for quantifying network cyclic structure to improve community detection
78
0
0.0
(
0
)
Added by
Behnaz Moradi-Jamei
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A distinguishing property of communities in networks is that cycles are more prevalent within communities than across communities. Thus, the detection of these communities may be aided through the incorporation of measures of the local richness of the cyclic structure. In this paper, we introduce renewal non-backtracking random walks (RNBRW) as a way of quantifying this structure. RNBRW gives a weight to each edge equal to the probability that a non-backtracking random walk completes a cycle with that edge. Hence, edges with larger weights may be thought of as more important to the formation of cycles. Of note, since separate random walks can be performed in parallel, RNBRW weights can be estimated very quickly, even for large graphs. We give simulation results showing that pre-weighting edges through RNBRW may substantially improve the performance of common community detection algorithms. Our results suggest that RNBRW is especially efficient for the challenging case of detecting communities in sparse graphs.
rate research
Read More
A distinguishing property of communities in networks is that cycles are more prevalent within communities than across communities. Thus, the detection of these communities may be aided through the incorporation of measures of the local richness of the cyclic structure. In this paper, we introduce renewal non-backtracking random walks (RNBRW) as a way of quantifying this structure. RNBRW gives a weight to each edge equal to the probability that a non-backtracking random walk completes a cycle with that edge. Hence, edges with larger weights may be thought of as more important to the formation of cycles. Of note, since separate random walks can be performed in parallel, RNBRW weights can be estimated very quickly, even for large graphs. We give simulation results showing that pre-weighting edges through RNBRW may substantially improve the performance of common community detection algorithms. Our results suggest that RNBRW is especially efficient for the challenging case of detecting communities in sparse graphs.
With invaluable theoretical and practical benefits, the problem of partitioning networks for community structures has attracted significant research attention in scientific and engineering disciplines. In literature, Newmans modularity measure is routinely applied to quantify the quality of a given partition, and thereby maximizing the measure provides a principled way of detecting communities in networks. Unfortunately, the exact optimization of the measure is computationally NP-complete and only applicable to very small networks. Approximation approaches have to be sought to scale to large networks. To address the computational issue, we proposed a new method to identify the partition decisions. Coupled with an iterative rounding strategy and a fast constrained power method, our work achieves tight and effective spectral relaxations. The proposed method was evaluated thoroughly on both real and synthetic networks. Compared with state-of-the-art approaches, the method obtained comparable, if not better, qualities. Meanwhile, it is highly suitable for parallel execution and reported a nearly linear improvement in running speed when increasing the number of computing nodes, which thereby provides a practical tool for partitioning very large networks.
In a graph, a community may be loosely defined as a group of nodes that are more closely connected to one another than to the rest of the graph. While there are a variety of metrics that can be used to specify the quality of a given community, one common theme is that flows tend to stay within communities. Hence, we expect cycles to play an important role in community detection. For undirected graphs, the importance of triangles -- an undirected 3-cycle -- has been known for a long time and can be used to improve community detection. In directed graphs, the situation is more nuanced. The smallest cycle is simply two nodes with a reciprocal connection, and using information about reciprocation has proven to improve community detection. Our new idea is based on the four types of directed triangles that contain cycles. To identify communities in directed networks, then, we propose an undirected edge-weighting scheme based on the type of the directed triangles in which edges are involved. We also propose a new metric on quality of the communities that is based on the number of 3-cycles that are split across communities. To demonstrate the impact of our new weighting, we use the standard METIS graph partitioning tool to determine communities and show experimentally that the resulting communities result in fewer 3-cycles being cut. The magnitude of the effect varies between a 10 and 50% reduction, and we also find evidence that this weighting scheme improves a task where plausible ground-truth communities are known.
A common goal in network modeling is to uncover the latent community structure present among nodes. For many real-world networks, observed connections consist of events arriving as streams, which are then aggregated to form edges, ignoring the temporal dynamic component. A natural way to take account of this temporal dynamic component of interactions is to use point processes as the foundation of the network models for community detection. Computational complexity hampers the scalability of such approaches to large sparse networks. To circumvent this challenge, we propose a fast online variational inference algorithm for learning the community structure underlying dynamic event arrivals on a network using continuous-time point process latent network models. We provide regret bounds on the loss function of this procedure, giving theoretical guarantees on performance. The proposed algorithm is illustrated, using both simulation studies and real data, to have comparable performance in terms of community structure in terms of community recovery to non-online variants. Our proposed framework can also be readily modified to incorporate other popular network structures.
There are several metrics (Modularity, Mutual Information, Conductance, etc.) to evaluate the strength of graph clustering in large graphs. These metrics have great significance to measure the effectiveness and they are often used to find the strongly connected clusters with respect to the whole graph. In this paper, we propose a new metric to evaluate the strength of graph clustering and also study its applications. We show that our proposed metric has great consistency which is similar to other metrics and easy to calculate. Our proposed metric also shows consistency where other metrics fail in some special cases. We demonstrate that our metric has reasonable strength while extracting strongly connected communities in both simulated (in silico) data and real data networks. We also show some comparative results of our proposed metric with other popular metric(s) for Online Social Networks (OSN) and Gene Regulatory Networks (GRN).
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
