Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS)

DOI: http://dx.doi.org/10.15439/2024F7644

Citation: Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 39, pages 609–614 (2024)

Full text

Abstract. We use a special edge centrality measure for node clustering in complex networks. The measure is based on the `spanning tree intersection' value motivated by previous work on the intersection and minimum expected overlap of random spanning trees in complex networks. First, we show that this new metric differs from some well-known edge centralities on random network models and real-world networks. Then, we show the applicability of the metric for clustering the nodes and point out some advantages over some other edge centrality based hierarchical clustering methods.

References

1. A. Gulyás, Z. Heszberger, and J. Biró, Paths: Why is life filled with so many detours? Springer Nature, 2021, http://dx.doi.org/10.1007/978-3-030-47545-1.
2. A. Gulyás, Z. Heszberger, J. Biró, A. Gulyás, Z. Heszberger, and J. Biró, “The universal nature of paths,” Paths, pp. 45–65, 2021.
3. A. Madkour, W. G. Aref, F. U. Rehman, M. A. Rahman, and S. Basalamah, “A survey of shortest-path algorithms,” arXiv preprint https://arxiv.org/abs/1705.02044, 2017.
4. L. M. Laskov and M. L. Marinov, “List of pareto optimal solutions of a biobjective shortest path problem,” in 2023 18th Conference on Computer Science and Intelligence Systems (FedCSIS). IEEE, 2023, pp. 603–613, http://dx.doi.org/10.15439/2023F3718.
5. A. Bóta, M. Krész, and A. Pluhár, “Dynamic communities and their detection,” Acta Cybernetica, vol. 20, pp. 35–52, 2011.
6. M. Girvan and M. E. Newman, “Community structure in social and biological networks,” PNAS, vol. 99, no. 12, pp. 7821–7826, 2002, http://dx.doi.org/10.1073/pnas.12265379.
7. P. G. Sun and Y. Yang, “Methods to find community based on edge centrality,” Physica A: Statistical Mechanics and its Applications, vol. 392, no. 9, pp. 1977–1988, 2013, http://dx.doi.org/10.1016/j.physa.2012.12.024.
8. M. E. Newman, “A measure of betweenness centrality based on random walks,” Social Networks, vol. 27, no. 1, pp. 39–54, 2005, http://dx.doi.org/10.1016/j.socnet.2004.11.009.
9. X. Qi, E. Fuller, R. Luo, and C.-q. Zhang, “A novel centrality method for weighted networks based on the kirchhoff polynomial,” Pattern Recognition Letters, vol. 58, pp. 51–60, 2015, http://dx.doi.org/10.1016/j.patrec.2015.02.007.
10. A. S. Teixeira, P. T. Monteiro, J. A. Carriço, M. Ramirez, and A. P. Francisco, “Spanning edge betweenness,” in Workshop on Mining and Learning with Graphs, vol. 24, 2013, pp. 27–31.
11. M. Gomez-Rodriguez, J. Leskovec, and A. Krause, “Inferring networks of diffusion and influence,” ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 5, no. 4, pp. 1–37, 2012.
12. S. Lämmer, B. Gehlsen, and D. Helbing, “Scaling laws in the spatial structure of urban road networks,” Physica A: Statistical Mechanics and its Applications, vol. 363, no. 1, pp. 89–95, 2006, http://dx.doi.org/10.1016/j.physa.2006.01.051.
13. C. Mavroforakis, R. Garcia-Lebron, I. Koutis, and E. Terzi, “Spanning edge centrality: Large-scale computation and applications,” in Proceedings of the 24th International Conference on World Wide Web, 2015, pp. 732–742, http://dx.doi.org/10.1145/2736277.2741125.
14. N. Albin, J. Clemens, D. Hoare, P. Poggi-Corradini, B. Sit, and S. Tymochko, “Fairest edge usage and minimum expected overlap for random spanning trees,” Discrete Mathematics, vol. 344, no. 5, p. 112282, 2021.
15. A. London and A. Pluhár, “Intersection of random spanning trees in small-world networks,” in International Conference on Complex Networks and Their Applications. Springer, 2022, pp. 337–345, http://dx.doi.org/10.1007/978-3-031-21131-7_26.
16. K. Kottegoda, Spanning tree modulus and secure broadcast games. PhD dissertation, Kansas State University, 2020.
17. E. W. Weisstein, “Matrix tree theorem,” https://mathworld.wolfram.com/, 2000.
18. A. Z. Broder, “Generating random spanning trees,” in FOCS, vol. 89, 1989, pp. 442–447, http://dx.doi.org/10.1109/SFCS.1989.63516.
19. D. B. Wilson, “Generating random spanning trees more quickly than the cover time,” in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996, pp. 296–303, http://dx.doi.org/10.1145/237814.237880.
20. A. Schild, “An almost-linear time algorithm for uniform random spanning tree generation,” in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 214–227.
21. J. H. Kim and V. H. Vu, “Generating random regular graphs,” in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, ser. STOC ’03, New York, NY, USA, 2003, p. 213–222.
22. A. Steger and N. C. Wormald, “Generating random regular graphs quickly,” Combinatorics, Probability and Computing, vol. 8, no. 4, p. 377–396, 1999, http://dx.doi.org/10.1017/S0963548399003867.
23. P. Erdős and A. Rényi, “On random graphs i.” Publicationes Mathematicae Debrecen, vol. 6, pp. 290–297, 1959, http://dx.doi.org/10.1515/9781400841356.38.
24. E. N. Gilbert, “Random graphs,” The Annals of Mathematical Statistics, vol. 30, no. 4, pp. 1141–1144, 1959.
25. A.-L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, pp. 509–512, 1999, http://dx.doi.org/10.1126/science.286.5439.509.
26. D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, pp. 440–442, 1998, http://dx.doi.org/10.1038/30918.
27. G. Gautier, G. Polito, R. Bardenet, and M. Valko, “DPPy: DPP Sampling with Python,” Journal of Machine Learning Research - Machine Learning Open Source Software (JMLR-MLOSS), 2019, http://github.com/guilgautier/DPPy/.
28. A. London and A. Pluhár, “Intersection of random spanning trees in complex networks,” Applied Network Science, vol. 8, no. 1, p. 72, 2023.
29. M. E. Newman, “Modularity and community structure in networks,” PNAS, vol. 103, no. 23, pp. 8577–8582, 2006.