Clique Relaxations in Social Network Analysis: The Maximum k -Plex Problem
Author
Abstract
Suggested Citation
DOI: 10.1287/opre.1100.0851
Download full text from publisher
References listed on IDEAS
- Barabási, Albert-László & Albert, Réka & Jeong, Hawoong, 2000. "Scale-free characteristics of random networks: the topology of the world-wide web," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 281(1), pages 69-77.
- Robert Mokken, 1979. "Cliques, clubs and clans," Quality & Quantity: International Journal of Methodology, Springer, vol. 13(2), pages 161-173, April.
- R. Luce, 1950. "Connectivity and generalized cliques in sociometric group structure," Psychometrika, Springer;The Psychometric Society, vol. 15(2), pages 169-190, June.
- Réka Albert & Hawoong Jeong & Albert-László Barabási, 2000. "Error and attack tolerance of complex networks," Nature, Nature, vol. 406(6794), pages 378-382, July.
- Laura A. Sanchis & Arun Jagota, 1996. "Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem," INFORMS Journal on Computing, INFORMS, vol. 8(2), pages 87-102, May.
- R. Luce & Albert Perry, 1949. "A method of matrix analysis of group structure," Psychometrika, Springer;The Psychometric Society, vol. 14(2), pages 95-116, June.
- S. S. Ravi & D. J. Rosenkrantz & G. K. Tayi, 1994. "Heuristic and Special Case Algorithms for Dispersion Problems," Operations Research, INFORMS, vol. 42(2), pages 299-310, April.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- Vladimir Boginski & Sergiy Butenko & Oleg Shirokikh & Svyatoslav Trukhanov & Jaime Gil Lafuente, 2014. "A network-based data mining approach to portfolio selection via weighted clique relaxations," Annals of Operations Research, Springer, vol. 216(1), pages 23-34, May.
- Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
- Zhou, Yi & Rossi, André & Hao, Jin-Kao, 2018. "Towards effective exact methods for the Maximum Balanced Biclique Problem in bipartite graphs," European Journal of Operational Research, Elsevier, vol. 269(3), pages 834-843.
- Zhou, Yi & Lin, Weibo & Hao, Jin-Kao & Xiao, Mingyu & Jin, Yan, 2022. "An effective branch-and-bound algorithm for the maximum s-bundle problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 27-39.
- Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2021. "A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1070-1090, July.
- Foad Mahdavi Pajouh & Zhuqi Miao & Balabhaskar Balasundaram, 2014. "A branch-and-bound approach for maximum quasi-cliques," Annals of Operations Research, Springer, vol. 216(1), pages 145-161, May.
- Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques," Working Papers 1723, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
- Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1722, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
- David Bergman & Andre A. Cire & Willem-Jan van Hoeve & J. N. Hooker, 2016. "Discrete Optimization with Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 47-66, February.
- Assif Assad & Kusum Deep, 2018. "A heuristic based harmony search algorithm for maximum clique problem," OPSEARCH, Springer;Operational Research Society of India, vol. 55(2), pages 411-433, June.
- Yuan Sun & Andreas Ernst & Xiaodong Li & Jake Weiner, 2021. "Generalization of machine learning for problem reduction: a case study on travelling salesman problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 607-633, September.
- Bruno Nogueira & Rian G. S. Pinheiro, 2020. "A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems," Annals of Operations Research, Springer, vol. 284(1), pages 367-400, January.
- Furini, Fabio & Ljubić, Ivana & Martin, Sébastien & San Segundo, Pablo, 2019. "The maximum clique interdiction problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 112-127.
- Fu, Wentao & Sun, Yang, 2021. "Rumor investigation in networks," Economic Modelling, Elsevier, vol. 98(C), pages 168-178.
- S. Raghavan & Rui Zhang, 2022. "Influence Maximization with Latency Requirements on Social Networks," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 710-728, March.
- Balasundaram, Balabhaskar & Borrero, Juan S. & Pan, Hao, 2022. "Graph signatures: Identification and optimization," European Journal of Operational Research, Elsevier, vol. 296(3), pages 764-775.
- François Fulconis & Didier Bédé & Laurence Saglietto & Joice de Almeira Goes & Gilles Paché & Raymundo Forradelas, 2014. "The entry of logistics service provider (LSP) into the wine industry supply chain," Post-Print hal-01062817, HAL.
- S. Raghavan & Rui Zhang, 2022. "Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1345-1365, May.
- Zhou, Qing & Benlic, Una & Wu, Qinghua, 2020. "An opposition-based memetic algorithm for the maximum quasi-clique problem," European Journal of Operational Research, Elsevier, vol. 286(1), pages 63-83.
- Zhuqi Miao & Balabhaskar Balasundaram, 2020. "An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 763-778, July.
- Stefano Coniglio & Stefano Gualandi, 2022. "Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1006-1023, March.
- Wayne Pullan, 2021. "Local search for the maximum k-plex problem," Journal of Heuristics, Springer, vol. 27(3), pages 303-324, June.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Veremyev, Alexander & Boginski, Vladimir, 2012. "Identifying large robust network clusters via new compact formulations of maximum k-club problems," European Journal of Operational Research, Elsevier, vol. 218(2), pages 316-326.
- Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Illya V. Hicks, 2016. "On the 2-Club Polytope of Graphs," Operations Research, INFORMS, vol. 64(6), pages 1466-1481, December.
- Vladimir Boginski & Sergiy Butenko & Oleg Shirokikh & Svyatoslav Trukhanov & Jaime Gil Lafuente, 2014. "A network-based data mining approach to portfolio selection via weighted clique relaxations," Annals of Operations Research, Springer, vol. 216(1), pages 23-34, May.
- Yuichi Asahiro & Tomohiro Kubo & Eiji Miyano, 2019. "Experimental Evaluation of Approximation and Heuristic Algorithms for Maximum Distance-Bounded Subgraph Problems," The Review of Socionetwork Strategies, Springer, vol. 13(2), pages 143-161, October.
- Zhuqi Miao & Balabhaskar Balasundaram, 2020. "An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 763-778, July.
- Pattillo, Jeffrey & Youssef, Nataly & Butenko, Sergiy, 2013. "On clique relaxation models in network analysis," European Journal of Operational Research, Elsevier, vol. 226(1), pages 9-18.
- Foad Mahdavi Pajouh & Zhuqi Miao & Balabhaskar Balasundaram, 2014. "A branch-and-bound approach for maximum quasi-cliques," Annals of Operations Research, Springer, vol. 216(1), pages 145-161, May.
- Balabhaskar Balasundaram & Sergiy Butenko & Svyatoslav Trukhanov, 2005. "Novel Approaches for Analyzing Biological Networks," Journal of Combinatorial Optimization, Springer, vol. 10(1), pages 23-39, August.
- Noah E. Friedkin, 1984. "Structural Cohesion and Equivalence Explanations of Social Homogeneity," Sociological Methods & Research, , vol. 12(3), pages 235-261, February.
- Morehead, Raymond & Noore, Afzel, 2007. "Novel hybrid mitigation strategy for improving the resiliency of hierarchical networks subjected to attacks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 378(2), pages 603-612.
- Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
- Rui Ding, 2019. "The Complex Network Theory-Based Urban Land-Use and Transport Interaction Studies," Complexity, Hindawi, vol. 2019, pages 1-14, June.
- Robert Mokken, 1979. "Cliques, clubs and clans," Quality & Quantity: International Journal of Methodology, Springer, vol. 13(2), pages 161-173, April.
- Cerqueti, Roy & Ferraro, Giovanna & Iovanella, Antonio, 2019. "Measuring network resilience through connection patterns," Reliability Engineering and System Safety, Elsevier, vol. 188(C), pages 320-329.
- Yezerska, Oleksandra & Mahdavi Pajouh, Foad & Butenko, Sergiy, 2017. "On biconnected and fragile subgraphs of low diameter," European Journal of Operational Research, Elsevier, vol. 263(2), pages 390-400.
- Vincent Labatut & Jean-Michel Balasque, 2012. "Detection and Interpretation of Communities in Complex Networks: Methods and Practical Application," Post-Print hal-00633653, HAL.
- Korotaev, Andrey (Коротаев, Андрей) & Shulgin, Sergey (Шульгин, Сергей) & Zinkina, Yulia (Зинькина, Юлия), 2017. "Country Risk Analysis Based on Demographic and Socio-Economic Data [Анализ Страновых Рисков С Использованием Демографических И Социально-Экономических Данных]," Working Papers 031715, Russian Presidential Academy of National Economy and Public Administration.
- Uroš Droftina & Mitja Å tular & Andrej Košir, 2015. "A diffusion model for churn prediction based on sociometric theory," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 9(3), pages 341-365, September.
- Orcun Temizkan & Sungjune Park & Cem Saydam, 2017. "Software Diversity for Improved Network Security: Optimal Distribution of Software-Based Shared Vulnerabilities," Information Systems Research, INFORMS, vol. 28(4), pages 828-849, December.
- Thang N. Dinh & Nam P. Nguyen & Md Abdul Alim & My T. Thai, 2015. "A near-optimal adaptive algorithm for maximizing modularity in dynamic scale-free networks," Journal of Combinatorial Optimization, Springer, vol. 30(3), pages 747-767, October.
More about this item
Keywords
maximum k-plex problem; maximum clique problem; social network analysis; clique relaxations; cohesive subgroups; scale-free graphs; power law graphs;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:59:y:2011:i:1:p:133-142. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.