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.
Code (1)
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
Ego-splitting Framework: from Non-Overlapping to Overlapping Clusters
We propose a new framework called Ego-Splitting for detecting clusters in complex networks which leverage the local structures known as ego-nets (i.e. the subgraph induced by the neighborhood of each node) to de-couple o…
ClusteringCommunity Detectiongraph partitioningHypothesis Testing for Automated Community Detection in Networks
Community detection in networks is a key exploratory tool with applications in a diverse set of areas, ranging from finding communities in social and biological networks to identifying link farms in the World Wide Web. T…
ClusteringCommunity DetectionTwo-sample testingOverlapping Community Detection Optimization and Nash Equilibrium
Community detection using both graphs and social networks is the focus of many algorithms. Recent methods aimed at optimizing the so-called modularity function proceed by maximizing relations within communities while min…
Community DetectionConstrained speaker linking
In this paper we study speaker linking (a.k.a.\ partitioning) given constraints of the distribution of speaker identities over speech recordings. Specifically, we show that the intractable partitioning problem becomes tr…
Speaker RecognitionSeed-Point Based Geometric Partitioning of Nuclei Clumps
When applying automatic analysis of fluorescence or histopathological images of cells, it is necessary to partition, or de-clump, partially overlapping cell nuclei. In this work, I describe a method of partitioning parti…