Flexi-clique: Exploring Flexible and Sub-linear Clique Structures
Pages 3832 - 3836
Abstract
Identifying cohesive subgraphs within networks is a fundamental problem in graph theory, relevant to various domains. The traditional clique problem, which finds fully connected subgraphs, often faces limitations due to its strict connectivity requirements. This paper introduces a novel degree-based relaxation model called Flexi-clique, where the degree constraint is adjusted sub-linearly based on the subgraph size. We establish that the maximum Flexi-clique problem is NP-hard and propose an efficient and effective peeling algorithm to address it. Our extensive experimental evaluation of real-world datasets demonstrates the effectiveness and efficiency of our approach in discovering large, cohesive subgraphs in networks.
References
[1]
James Abello, Mauricio GC Resende, and Sandra Sudarsky. 2002. Massive quasi-clique detection. In LATIN 2002: Theoretical Informatics: 5th Latin American Symposium Cancun, Mexico, April 3--6, 2002 Proceedings 5. Springer, 598--612.
[2]
Mohammed Alokshiya, Saeed Salem, and Fidaa Abed. 2018. A linear delay linear space algorithm for enumeration of all connected induced subgraphs. In Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics. 607--607.
[3]
Balabhaskar Balasundaram, Sergiy Butenko, and Illya V Hicks. 2011. Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research, Vol. 59, 1 (2011), 133--142.
[4]
Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. science, Vol. 286, 5439 (1999), 509--512.
[5]
Vladimir Batagelj and Matjaz Zaversnik. 2003. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049 (2003).
[6]
Vladimir Boginski, Sergiy Butenko, and Panos M Pardalos. 2006. Mining market data: A network approach. Computers & Operations Research, Vol. 33, 11 (2006), 3171--3184.
[7]
Lijun Chang. 2019. Efficient maximum clique computation over large sparse graphs. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 529--538.
[8]
Eunjoon Cho, Seth A Myers, and Jure Leskovec. 2011. Friendship and mobility: user movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 1082--1090.
[9]
Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. 2009. Power-law distributions in empirical data. SIAM review, Vol. 51, 4 (2009), 661--703.
[10]
William HE Day and David Sankoff. 1986. Computational complexity of inferring phylogenies by compatibility. Systematic Biology, Vol. 35, 2 (1986), 224--229.
[11]
Ulrich Dorndorf, Florian Jaehn, and Erwin Pesch. 2008. Modelling robust flight-gate scheduling as a clique partitioning problem. Transportation Science, Vol. 42, 3 (2008), 292--301.
[12]
Tuvi Etzion and Patric RJ Ostergard. 1998. Greedy and heuristic algorithms for codes and colorings. IEEE Transactions on Information Theory, Vol. 44, 1 (1998), 382--388.
[13]
Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. 2008. Benchmark graphs for testing community detection algorithms. Physical review E, Vol. 78, 4 (2008), 046110.
[14]
Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. 2020. Mining of massive data sets. Cambridge university press.
[15]
R Duncan Luce. 1950. Connectivity and generalized cliques in sociometric group structure. Psychometrika, Vol. 15, 2 (1950), 169--190.
[16]
R Duncan Luce and Albert D Perry. 1949. A method of matrix analysis of group structure. Psychometrika, Vol. 14, 2 (1949), 95--116.
[17]
Zhuqi Miao and Balabhaskar Balasundaram. 2017. Approaches for finding cohesive subgroups in large-scale social networks via maximum k-plex detection. Networks, Vol. 69, 4 (2017), 388--407.
[18]
Robert J Mokken et al. 1979. Cliques, clubs and clans. Quality & Quantity, Vol. 13, 2 (1979), 161--173.
[19]
Satu Elisa Schaeffer. 2007. Graph clustering. Computer science review, Vol. 1, 1 (2007), 27--64.
[20]
Stephen B Seidman. 1983. Network structure and minimum degree. Social networks, Vol. 5, 3 (1983), 269--287.
[21]
Stephen B Seidman and Brian L Foster. 1978. A graph-theoretic generalization of the clique concept. Journal of Mathematical sociology, Vol. 6, 1 (1978), 139--154.
[22]
Georg Simmel. 1950. The sociology of georg simmel. Vol. 92892. Simon and Schuster.
[23]
Jaewon Yang and Jure Leskovec. 2012. Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. 1--8.
[24]
Wayne W Zachary. 1977. An information flow model for conflict and fission in small groups. Journal of anthropological research, Vol. 33, 4 (1977), 452--473.
Index Terms
- Flexi-clique: Exploring Flexible and Sub-linear Clique Structures
Recommendations
Clique-transversal sets and clique-coloring in planar graphs
Let G=(V,E) be a graph. A clique-transversal setD is a subset of vertices of G such that D meets all cliques of G, where a clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. The clique-transversal number, ...
On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcon, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition ...
The clique-perfectness and clique-coloring of outer-planar graphs
AbstractA clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2024
5705 pages
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 October 2024
Check for updates
Author Tags
Qualifiers
- Short-paper
Funding Sources
- National Research Foundation of Korea
- Institute of Information & communications Technology Planning & Evaluation
- UNIST Settlement Research fund
Conference
CIKM '24
Sponsor:
CIKM '24: The 33rd ACM International Conference on Information and Knowledge Management
October 21 - 25, 2024
ID, Boise, USA
Acceptance Rates
Overall Acceptance Rate 1,861 of 8,427 submissions, 22%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 83Total Downloads
- Downloads (Last 12 months)83
- Downloads (Last 6 weeks)83
Reflects downloads up to 23 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in