Dynamic Parameter Selection for Community Detection Algorithms (Graph Networks)

RT&L FOCUS AREA(S): INFORMATION SYSTEMS TECHNOLOGY AREA(S): AUTONOMY OBJECTIVE: Establish a general approach for dynamically setting the tuning parameter for a given community detection (CD) algorithm and graph. Validate the approach on four algorithms with novel data provided by the National Geospatial Intelligence Agency (NGA) . DESCRIPTION: NGA produces timely, accurate, and actionable geospatial intelligence to support U.S. national security. NGA works with a variety of data types including graph networks, which can be used to analyze computer, biological, and social networks. One of the fundamental problems in graph networks is CD. About half of all CD algorithms require a tuning parameter. For example, the Walktrap [1] algorithm finds communities by taking random walks on the graph, but the user must define the length of the walks. For the purposes of this solicitation, we are investigating the four CD algorithms in Table 1. Table 1 CD algorithms and their parameters. Time complexity is provided in terms of n (number of nodes) and m (number of edges). All four algorithms are available in the igraph library [5]. CD algorithm Tuning parameter Time complexity Walktrap [1] num_steps O(mn2) Spinglass [2] gamma O(n3.2) Leiden [3] gamma O(nlog(n)) FluidC [4] num_communities O(m) In real-world scenarios (where ground truth is not available) parameter selection is performed by maximizing a heuristic like modularity [6]. However, this approach has several limitations. First, modularity is unable to resolve small communities in large networks, even when they are well-defined [7]. Second, the brute-force approach to parameter tuning is computationally inefficient because it requires running the algorithm multiple times. The purpose of this solicitation is to develop a method for dynamically setting the parameter value for a given CD algorithm based only on observable features of the graph (e.g., number of nodes, degree distribution, average diameter, centrality measures, or clustering coefficient [8]). This approach reduces the overall time required to process large graphs by avoiding a brute-force search, facilitates automation of the CD algorithms, and advances research in parameter selection for graph network algorithms. Please note that NGA prefers proposals whose dynamic parameter selection solutions generalize beyond CD algorithms and even beyond the graph network domain. CD algorithms that are parameter-free (e.g., Fastgreedy, Infomap, Label propagation, or Edge betweenness see [9]) or based on deep learning [10] are out of scope for Phase I. Communities are defined as subgroups of nodes that are more densely connected internally than with the rest of the network, suggesting that the network has certain natural divisions within it. PHASE I: Design and develop a method for dynamically setting the parameter value for a given CD algorithm and graph. Test the proposed approach on the four CD algorithms listed in Table 1. NGA will evaluate funded proposals using test graphs for which NGA knows the ground truth. For each test graph, performers must choose one tuning parameter for each of the four CD algorithms. The performers' scores and an analysis of the time complexity of their approaches will determine who is funded in Phase II. PHASE II: Validate the generalizability of the proposed approach by dynamically setting the parameter value for at least two other graph algorithms (i.e., not CD algorithms). Performers will be responsible for selecting the target algorithms and performing experiments that validate their approach. PHASE III DUAL USE APPLICATIONS: The ability to automate algorithms that otherwise require human input is of significant commercial value. This technology could be used to create new features for existing software products or automate human-driven processes. REFERENCES: [1] P. Pons and M. Latapy, Computing communities in large networks using random walks (long version), arXiv:physics/0512106, Dec. 2005 [Online]. Available: http://arxiv.org/abs/physics/0512106. [2] J. Reichardt and S. Bornholdt, Statistical Mechanics of Community Detection, Phys. Rev. E, vol. 74, no. 1, p. 016110, Jul. 2006, doi: 10.1103/PhysRevE.74.016110. [3] V. A. Traag, L. Waltman, and N. J. van Eck, From Louvain to Leiden: guaranteeing well-connected communities, Scientific Reports, vol. 9, no. 1, p. 5233, Mar. 2019, doi: 10.1038/s41598-019-41695-z. [4] F. Par s et al., Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm, in Complex Networks & Their Applications VI, Cham, 2018, pp. 229 240, doi: 10.1007/978-3-319-72150-7_19. [5] G. Csardi, The igraph software package for complex network research, Int J Complex Syst, vol. 1695, 2006 [Online]. Available: https://igraph.org/. [6] M. E. J. Newman, Modularity and community structure in networks, Proc Natl Acad Sci U S A, vol. 103, no. 23, pp. 8577 8582, Jun. 2006, doi: 10.1073/pnas.0601602103. [7] A. Lancichinetti and S. Fortunato, Limits of modularity maximization in community detection, Phys. Rev. E, vol. 84, no. 6, p. 066122, Dec. 2011, doi: 10.1103/PhysRevE.84.066122. [8] L. Peel, Estimating network parameters for selecting community detection algorithms, in 2010 13th International Conference on Information Fusion, 2010, pp. 1 8, doi: 10.1109/ICIF.2010.5712065. [9] Z. Yang, R. Algesheimer, and C. J. Tessone, A Comparative Analysis of Community Detection Algorithms on Artificial Networks, Scientific Reports, vol. 6, no. 1, p. 30750, Aug. 2016, doi: 10.1038/srep30750. [10] F. Liu et al., Deep Learning for Community Detection: Progress, Challenges and Opportunities, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, pp. 4981 4987, Jul. 2020, doi: 10.24963/ijcai.2020/693.