Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
The DOI matches its Crossref record; 56 of the 56 references it cites were found in a registry or an index.
Abstract
This paper introduces and studies the maximum k-plex problem, which arises in social network analysis and has wider applicability in several important areas employing graph-based data mining. After establishing NP-completeness of the decision version of the problem on arbitrary graphs, an integer programming formulation is presented, followed by a polyhedral study to identify combinatorial valid inequalities and facets. A branch-and-cut algorithm is implemented and tested on proposed benchmark instances. An algorithmic approach is developed exploiting the graph-theoretic properties of a k-plex that is effective in solving the problem to optimality on very large, sparse graphs such as the power law graphs frequently encountered in the applications of interest.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Harary, F. (1969) · Cited by 10,739
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35019019 · Cited by 7,534
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-Ĺ. (2000) · RePEc: Research Papers in Economics · Cited by 6,469
(2017) · The SAGE Encyclopedia of Communication Research Methods · doi:10.4135/9781483381411.n575 · Cited by 6,008
Social Network Analysis: A Handbook.
Pappi, F. U., & Scott, J. (1993) · Contemporary Sociology · doi:10.2307/2075047 · Cited by 5,969
Lethality and centrality in protein networks
Jeong, H., Mason, S. P., Barabási, A.-L., & Oltvai, Z. N. (2001) · Nature · doi:10.1038/35075138 · Cited by 5,287
A comprehensive two-hybrid analysis to explore the yeast protein interactome
Ito, T., Chiba, T., Ozawa, R., Yoshida, M., Hattori, M., & Sakaki, Y. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.061034498 · Cited by 3,566
Network structure and minimum degree
Seidman, S. B. (1983) · Social Networks · doi:10.1016/0378-8733(83)90028-x · Cited by 1,891
Protein complexes and functional modules in molecular networks
Spirin, V., & Mirny, L. A. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2032324100 · Cited by 1,461
Scale-free characteristics of random networks: the topology of the world-wide web
Barabási, A.-L., Albert, R., & Jeong, H. (2000) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(00)00018-2 · Cited by 1,408
Cluster analysis for gene expression data: a survey
Jiang, D., Tang, C., & Zhang, A. (2004) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2004.68 · Cited by 1,235
Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_1 · Cited by 1,148
The protein–protein interaction map of Helicobacter pylori
Rain, J.-C., Selig, L., De Reuse, H., Battaglia, V., Reverdy, C., Simon, S., Lenzen, G., Petel, F., Wojcik, J., Schächter, V., et al. (2001) · Nature · doi:10.1038/35051615 · Cited by 1,146
A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
Padberg, M., & Rinaldi, G. (1991) · SIAM Review · doi:10.1137/1033004 · Cited by 1,097
Power-Law Distribution of the World Wide Web
Adamic, L. A., & Huberman, B. A. (2000) · Science · doi:10.1126/science.287.5461.2115a · Cited by 1,015
CBMS-NSF REGIONAL CONFERENCE SERIES IN APPLIED MATHEMATICS
Gottlieb, D., Orszag, S. A., Huber, P. J., & Roberts, F. S. (2011) · Cited by 999
Mapping Networks of Terrorist Cells
Krebs, V. E. (2001) · Cited by 995
A Method of Matrix Analysis of Group Structure
Luce, R. D., & Perry, A. D. (1949) · Psychometrika · doi:10.1007/bf02289146 · Cited by 983
Moon, J. W., & Moser, L. (1965) · Israel Journal of Mathematics · doi:10.1007/bf02760024 · Cited by 837
Chung, F., & Lu, L. (2006) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/107 · Cited by 700
On the facial structure of set packing polyhedra
Padberg, M. W. (1973) · Mathematical Programming · doi:10.1007/bf01580121 · Cited by 596
A fast algorithm for the maximum clique problem
Östergård, P. R. J. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00290-6 · Cited by 590
The application of network analysis to criminal intelligence: An assessment of the prospects
Sparrow, M. K. (1991) · Social Networks · doi:10.1016/0378-8733(91)90008-h · Cited by 564
Crime data mining: a general framework and some examples
Chen, H., Chung, W., Xu, J. J., Wang, G., Qin, Y., & Chau, M. (2004) · Computer · doi:10.1109/mc.2004.1297301 · Cited by 542
A graph‐theoretic definition of a sociometric clique†
Alba, R. D. (1973) · The Journal of Mathematical Sociology · doi:10.1080/0022250x.1973.9989826 · Cited by 497
Cliques, Coloring, and Satisfiability
(1996) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/026 · Cited by 476
Gaining confidence in high-throughput protein interaction networks
Bader, J. S., Chaudhuri, A., Rothberg, J. M., & Chant, J. (2004) · Nature Biotechnology · doi:10.1038/nbt924 · Cited by 467
A graph‐theoretic generalization of the clique concept
Seidman, S. B., & Foster, B. L. (1978) · Journal of Mathematical Sociology · doi:10.1080/0022250x.1978.9989883 · Cited by 464
Handbook of Wireless Networks and Mobile Computing
Stojmenović, I. (2002) · Wiley eBooks · doi:10.1002/0471224561 · Cited by 453
State of the art of graph-based data mining
Washio, T., & Motoda, H. (2003) · ACM SIGKDD Explorations Newsletter · doi:10.1145/959242.959249 · Cited by 448
Cook, D. J., & Holder, L. B. (2000) · IEEE Intelligent Systems and their Applications · doi:10.1109/5254.850825 · Cited by 442
Statistical analysis of financial networks
Boginski, V., Butenko, S., & Pardalos, P. M. (2005) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2004.02.004 · Cited by 409
Self-citationMokken, R. J. (1979) · Quality & Quantity · doi:10.1007/bf00139635 · Cited by 374
Connectivity and Generalized Cliques in Sociometric Group Structure
Luce, R. D. (1950) · Psychometrika · doi:10.1007/bf02289199 · Cited by 343
Massive Quasi-Clique Detection
Abello, J., Resende, M. G. C., & Sudarsky, S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45995-2_51 · Cited by 331
On the solution of traveling salesman problems
Chvátal, V., Cook, W. J., Applegate, D., & Bixby, R. E. (1998) · EMS Press eBooks · doi:10.4171/dms/1-3/62 · Cited by 328
Mining market data: A network approach
Boginski, V., Butenko, S., & Pardalos, P. M. (2006) · Computers & Operations Research · doi:10.1016/j.cor.2005.01.027 · Cited by 283
Self-citationStudying Complex Discursive Systems..: Centering Resonance Analysis of Communication
Corman, S. R., Kuhn, T., Mcphee, R. D., & Dooley, K. J. (2002) · Human Communication Research · doi:10.1111/j.1468-2958.2002.tb00802.x · Cited by 274
The Sociological Concept of "Group": An Empirical Test of Two Models
Freeman, L. C. (1992) · American Journal of Sociology · doi:10.1086/229972 · Cited by 249
On maximum clique problems in very large graphs
Abello, J., Pardalos, P., & Resende, M. (1999) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/050/06 · Cited by 221
Internet topology: connectivity of IP graphs:
Broido, A., & claffy, K. (2001) · SPIE Proceedings · doi:10.1117/12.434393 · Cited by 163
Clique-detection models in computational biochemistry and genomics
Butenko, S., & Wilhelm, W. E. (2006) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.05.026 · Cited by 162
Self-citationA class of facet producing graphs for vertex packing polyhedra
Trotter, L. E. (1975) · Discrete Mathematics · doi:10.1016/0012-365x(75)90077-1 · Cited by 161
Novel Approaches for Analyzing Biological Networks
Balasundaram, B., Butenko, S. I., & Trukhanov, S. (2005) · Journal of Combinatorial Optimization · doi:10.1007/s10878-005-1857-x · Cited by 143
Self-citationModular decomposition of protein-protein interaction networks
Gagneur, J., Krause, R., Bouwmeester, T., & Casari, G. (2004) · Genome biology · doi:10.1186/gb-2004-5-8-r57 · Cited by 135
Constructing, organizing, and visualizing collections of topically related Web resources
Terveen, L., Hill, W., & Amento, B. S. (1999) · ACM Transactions on Computer-Human Interaction · doi:10.1145/310641.310644 · Cited by 101
OR FORUM—Catching the “Network Science” Bug: Insight and Opportunity for the Operations Researcher
Alderson, D. (2008) · Operations Research · doi:10.1287/opre.1080.0606 · Cited by 93
The Structural Analysis of Criminal Networks
McAndrew, D. (2021) · Routledge eBooks · doi:10.4324/9781315237022-3 · Cited by 82
Combinatorial Genetic Regulatory Network Analysis Tools for High Throughput Transcriptomic Data
Chesler, E. J., & Langston, M. A. (2007) · Springer eBooks · doi:10.1007/978-3-540-48540-7_13 · Cited by 72
Test case generators and computational results for the maximum clique problem
Hasselberg, J., Pardalos, P. M., & Vairaktarakis, G. L. (1993) · Journal of Global Optimization · doi:10.1007/bf01096415 · Cited by 68
The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
Yannakakis, M. (1979) · Journal of the ACM · doi:10.1145/322154.322157 · Cited by 63
Power Laws in Biological Networks
Almaas, E., & Barabási, A.-Ĺ. (2007) · Springer eBooks · doi:10.1007/0-387-33916-7_1 · Cited by 44
Graph based molecular data mining - an overview
Fischer, I., & Meinl, T. (2005) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.2004.1401253 · Cited by 42
Cited by
A classification for community discovery methods in complex networks
Coscia, M., Giannotti, F., & Pedreschi, D. (2011) · Statistical Analysis and Data Mining: The ASA Data Science Journal · doi:10.1002/sam.10133 · Cited by 353
A survey of community search over big graphs
Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., & Lin, X. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00556-x · Cited by 339
Camacho, D., Panizo-LLedot, Á., Bello-Orgaz, G., Gonzalez-Pardo, A., & Cambria, E. (2020) · Information Fusion · doi:10.1016/j.inffus.2020.05.009 · Cited by 329
A review on algorithms for maximum clique problems
Wu, Q., & Hao, J.-K. (2015) · European Journal of Operational Research · doi:10.1016/j.ejor.2014.09.064 · Cited by 314
Applications of near-term photonic quantum computers: software and algorithms
Bromley, T. R., Arrazola, J. M., Jahangiri, S., Izaac, J., Quesada, N., Gran, A. D., Schuld, M., Swinarton, J., Zabaneh, Z., & Killoran, N. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8504 · Cited by 128
Metadata
- Authors
- Balasundaram, B., Butenko, S., & Hicks, I. V.
- Venue
- Operations Research
- Published
- 2011-02
- Volume
- 59
- Issue
- 1
- Pages
- 133-142
- ISSN
- 0030-364X (ISSN-L)
- 1526-5463
- OpenAlex
- W2169088933
- Cited by
- 302
- References
- 56
- FWCI
- 14.65
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.