A Community Detection Method based on Formal Concept Lattice

Tiantian Wang; Zhenhao Qi; Zhicheng Ding

doi:10.54097/7zkzbv75

Authors

Tiantian Wang
Zhenhao Qi
Zhicheng Ding

DOI:

https://doi.org/10.54097/7zkzbv75

Keywords:

Community Detection, Concept Lattice, Greedy Covering, Network Analysis

Abstract

Community detection aims to uncover groups of vertices in a network that are more closely connected to each other than to the rest of the graph. While many existing algorithms rely purely on structural information, additional insights can be gained by incorporating conceptual relationships among nodes. This paper presents a community detection framework based on classical concept lattices. The method constructs a lattice from the given context, employs a greedy covering strategy to identify representative communities, and applies a merging mechanism to refine the results. Experiments on synthetic and real-world networks show that the proposed approach produces stable and interpretable communities, demonstrating the potential of concept lattice theory as a tool for network analysis.

Downloads

Download data is not yet available.

References

[1] J. van der Geer, J.A.J. Hanraads, R.A. Lupton, The art of writing a scientific article, J. Sci. Commun. 163 (2000) 51-59.

[2] Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. Proceedings of the national academy of sciences 105(4), 1118–1123 (2008).

[3] Fortunato, S.: Community detection in graphs. Physics reports 486(3-5), 75–174(2010).

[4] Fortunato, S., Hric, D.: Community detection in networks: A user guide. Physics reports 659, 1–44 (2016).

[5] Traag, V., Waltman, L., Van Eck, N.: From Louvain to Leiden: guaranteeing well-connected communities. Sci. Rep. 9, 5233 (2019).

[6] Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, pp. 1–8 (2012).

[7] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609. 02907 (2016).

[8] Lancichinetti, A., Fortunato, S.: Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys- ical Review E—Statistical, Nonlinear, and Soft Matter Physics 80(1), 016118 (2009).

[9] Peel, L., Larremore, D.B., Clauset, A.: The ground truth about metadata and community detection in networks. Science advances 3(5), 1602548 (2017).

[10] Xie, J., Kelley, S., Szymanski, B.K.: Overlapping community detection in net- works: The state-of-the-art and comparative study. Acm computing surveys (csur) 45(4), 1–35 (2013).

[11] Zhang, X., Liu, H., Li, Q., Wu, X.M.: Attributed graph clustering via adaptive graph convolution. In: 28th International Joint Conference on Artificial Intel- ligence, IJCAI 2019, pp. 4327–4333 (2019). International Joint Conferences on Artificial Intelligence.

[12] Stacey, R.G., Skinnider, M.A., Foster, L.J.: On the robustness of graph-based clustering to random network alterations. Molecular & Cellular Proteomics 20 (2021).

[13] Wille, R.: Restructuring lattice theory: An approach based on hierarchies of concepts. In: Rival, I. (ed.) Ordered Sets, pp. 445–470. Springer, Dordrecht (1982).

[14] Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer (1997).

[15] Ren, R., Wei, L.: The attribute reductions of three-way concept lattices. Knowledge-Based Systems 99, 92–102 (2016).

[16] Zhang, H.-R., Min, F.: Three-way recommender systems based on random forests. Knowledge-Based Systems 91, 275–286 (2016).

[17] Yu, H., Li, Q., Cai, M.: Characteristics of three-way concept lattices and three-way rough concept lattices. Knowledge-Based Systems 146, 181–189 (2018).

[18] Lang, G., Luo, J., Yao, Y.: Three-way conflict analysis: a unification of models based on rough sets and formal concept analysis. Knowledge-Based Systems 194, 105556 (2020).

[19] Lang, G., Yao, Y.: Formal concept analysis perspectives on three-way conflict analysis. International Journal of Approximate Reasoning 152, 160–182 (2023).

[20] Zhi, H., Qi, J., Qian, T., Wei, L.: Three-way dual concept analysis. International Journal of Approximate Reasoning 114, 151–165 (2019).

[21] Zhi, H., Li, J., Li, Y.: Multilevel conflict analysis based on fuzzy formal contexts. IEEE Transactions on Fuzzy Systems 30(12), 5128–5142 (2022).

[22] Qi, Z., Zhi, H., Ding, W.: Distributed conflict analysis across varying analysis levels based on fuzzy formal contexts. Information Sciences 707, 122038 (2025).

[23] Wu, J., Tsang, E.C., Xu, W., Zhang, C., Yang, L.: Correlation concept-cognitive learning model for multi-label classification. Knowledge-Based Systems 290, 111566 (2024).