EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Performance of community detection algorithms supported by node embeddings

Bartosz Pankratz, Bogumił Kamiński, Paweł Prałat

Journal of Complex Networks · 24.06.2024 · 12 (4)

DOI: 10.1093/comnet/cnae035 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Complex Networks, online erschienen am 20.08.2024. Verfasst von Bartosz Pankratz und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 50 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The grouping of nodes into subsets that are relatively densely interconnected and separable from the rest of the network is a property often displayed in many complex real-world networks; this feature is known as a community structure. There is a growing demand for algorithms that can find partitions that resemble the community structure of a given network as closely as possible. However, most popular algorithms for community detection in graphs have one serious drawback, namely, they are heuristic-based and in many cases are unable to find a near-optimal solution. Moreover, their results are volatile, impacting the replicability of their results. In this paper, we investigate if the performance of greedy algorithms might be improved by initialising such algorithms with some carefully chosen partition of nodes, namely a partition obtained by embedding the nodes into real numbers space and then running a clustering algorithm on this latent representation. We believe that embedding will filter unwanted noise while retaining the proximity of nodes belonging to the same community or will learn more complex and elusive relations between nodes. Then, clustering algorithms run on this embedding will create a stable partitioning that will reduce the uncertainty in the initial phases of the community detection algorithms. The experiments show that the proposed procedure significantly improves the results over baseline community detection algorithms, namely Louvain and Leiden. It also reduces the inherent volatility of such algorithms. The impact depends on the given graph’s properties, especially the strength of the community structure and degree distribution. The largest boost in performance is given in the cases when networks are ‘noisier’, that is, when the community structure is less pronounced and there are many connections between communities. Furthermore, the design and parametrization of the procedure depend on the network’s topology, not on the size of the network itself.

Zitieren

APA

Pankratz, B., Kamiński, B., & Prałat, P. (2024). Performance of community detection algorithms supported by node embeddings. Journal of Complex Networks, 12(4). https://doi.org/10.1093/comnet/cnae035

Vancouver

Pankratz B, Kamiński B, Prałat P. Performance of community detection algorithms supported by node embeddings. Journal of Complex Networks. 2024;12(4). doi:10.1093/comnet/cnae035

BibTeX
@article{Pankratz2024,
  author = {Pankratz, Bartosz and Kamiński, Bogumił and Prałat, Paweł},
  title = {Performance of community detection algorithms supported by node embeddings},
  journal = {Journal of Complex Networks},
  year = {2024},
  volume = {12},
  number = {4},
  doi = {10.1093/comnet/cnae035}
}
Kostenlos starten →