Local community detection based on small cliques
type: Item
instance of: scholarly article
title: Local community detection based on small cliques
zbMATH Open document ID: 1433.68297
author: Michael Hamann
author: Eike Röhrs
author: Dorothea Wagner
published in: Algorithms
publication date: 2018-08-13T00:00:00Z
review text: Summary: Community detection aims to find dense subgraphs in a network. We consider the problem of finding a community locally around a seed node both in unweighted and weighted networks. This is a faster alternative to algorithms that detect communities that cover the whole network when actually only a single community is required. Further, many overlapping community detection algorithms use local community detection algorithms as basic building block. We provide a broad comparison of different existing strategies of expanding a seed node greedily into a community. For this, we conduct an extensive experimental evaluation both on synthetic benchmark graphs as well as real world networks. We show that results both on synthetic as well as real-world networks can be significantly improved by starting from the largest clique in the neighborhood of the seed node. Further, our experiments indicate that algorithms using scores based on triangles outperform other algorithms in most cases. We provide theoretical descriptions as well as open source implementations of all algorithms used.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C82
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6916749
zbMATH Keywords: community detection
zbMATH Keywords: local community
zbMATH Keywords: clique
zbMATH Keywords: iterative expansion
describes a project that uses: NetworKit
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a10030090
OpenAlex ID: W2742266097
cites work: Graph clustering
cites work: Local community detection in complex networks based on maximum cliques extension
cites work: LOCAL COMMUNITY IDENTIFICATION IN SOCIAL NETWORKS
cites work: Collective dynamics of ‘small-world’ networks
cites work: Q4931752
cites work: Arboricity, \(h\)-index, and dynamic algorithms
cites work: Listing All Maximal Cliques in Large Sparse Real-World Graphs
cites work: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
cites work: The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
DOI: 10.3390/A10030090
description: scientific article; zbMATH DE number 6916749