Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userModularity based community detection in heterogeneous networks
109
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Heterogeneous networks are networks consisting of different types of nodes and multiple types of edges linking such nodes. While community detection has been extensively developed as a useful technique for analyzing networks that contain only one type of nodes, very few community detection techniques have been developed for heterogeneous networks. In this paper, we propose a modularity based community detection framework for heterogeneous networks. Unlike existing methods, the proposed approach has the flexibility to treat the number of communities as an unknown quantity. We describe a Louvain type maximization method for finding the community structure that maximizes the modularity function. Our simulation results show the advantages of the proposed method over existing methods. Moreover, the proposed modularity function is shown to be consistent under a heterogeneous stochastic blockmodel framework. Analyses of the DBLP four-area dataset and a MovieLens dataset demonstrate the usefulness of the proposed method.
rate research
Read More
There has been a surge of interest in community detection in homogeneous single-relational networks which contain only one type of nodes and edges. However, many real-world systems are naturally described as heterogeneous multi-relational networks which contain multiple types of nodes and edges. In this paper, we propose a new method for detecting communities in such networks. Our method is based on optimizing the composite modularity, which is a new modularity proposed for evaluating partitions of a heterogeneous multi-relational network into communities. Our method is parameter-free, scalable, and suitable for various networks with general structure. We demonstrate that it outperforms the state-of-the-art techniques in detecting pre-planted communities in synthetic networks. Applied to a real-world Digg network, it successfully detects meaningful communities.
Community detection is a significant and challenging task in network research. Nowadays, plenty of attention has been focused on local methods of community detection. Among them, community detection with a greedy algorithm typically starts from the identification of local essential nodes called central nodes of the network; communities expand later from these central nodes by optimizing a modularity function. In this paper, we propose a new central node indicator and a new modularity function. Our central node indicator, which we call local centrality indicator (LCI), is as efficient as the well-known global maximal degree indicator and local maximal degree indicator; on certain special network structure, LCI performs even better. On the other hand, our modularity function F2 overcomes certain disadvantages,such as the resolution limit problem,of the modularity functions raised in previous literature. Combined with a greedy algorithm, LCI and F2 enable us to identify the right community structures for both the real world networks and the simulated benchmark network. Evaluation based on the normalized mutual information (NMI) suggests that our community detection method with a greedy algorithm based on LCI and F2 performs superior to many other methods. Therefore, the method we proposed in this paper is potentially noteworthy.
Identifying communities in networks is a fundamental and challenging problem of practical importance in many fields of science. Current methods either ignore the heterogeneous distribution of nodal degrees or assume prior knowledge of the number of communities. Here we propose an efficient hypothesis test for community detection based on quantifying dissimilarities between graphs. Given a random graph, the null hypothesis is that it is of degree-corrected Erd{o}s-R{e}nyi type. We compare the dissimilarity between them by a measure incorporating the vertex distance distribution, the clustering coefficient distribution, and the alpha-centrality distribution, which is used for our hypothesis test. We design a two-stage bipartitioning algorithm to uncover the number of communities and the corresponding structure simultaneously. Experiments on synthetic and real networks show that our method outperforms state-of-the-art ones.
In many complex systems, networks and graphs arise in a natural manner. Often, time evolving behavior can be easily found and modeled using time-series methodology. Amongst others, two common research problems in network analysis are community detection and change-point detection. Community detection aims at finding specific sub-structures within the networks, and change-point detection tries to find the time points at which sub-structures change. We propose a novel methodology to detect both community structures and change points simultaneously based on a model selection framework in which the Minimum Description Length Principle (MDL) is utilized as minimizing objective criterion. The promising practical performance of the proposed method is illustrated via a series of numerical experiments and real data analysis.
The maximization of generalized modularity performs well on networks in which the members of all communities are statistically indistinguishable from each other. However, there is no theory bounding the maximization performance in more realistic networks where edges are heterogeneously distributed within and between communities. Using the random graph properties, we establish asymptotic theoretical bounds on the resolution parameter for which the generalized modularity maximization performs well. From this new perspective on random graph model, we find the resolution limit of modularity maximization can be explained in a surprisingly simple and straightforward way. Given a network produced by the stochastic block models, the communities for which the resolution parameter is larger than their densities are likely to be spread among multiple clusters, while communities for which the resolution parameter is smaller than their background inter-community edge density will be merged into one large component. Therefore, no suitable resolution parameter exits when the intra-community edge density in a subgraph is lower than the inter-community edge density in some other subgraph. For such networks, we propose a progressive agglomerative heuristic algorithm to detect practically significant communities at multiple scales.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
