Abstract
Clique relaxation models that were originally introduced in the literature on social network analysis are not only gaining increasing popularity in a wide spectrum of complex network applications, but also keep garnering attention of mathematicians, computer scientists, and operations researchers as a promising avenue for fruitful theoretical investigations. This chapter describes the origins of clique relaxation concepts and provides a brief overview of mathematical programming formulations for the corresponding optimization problems, algorithms proposed to solve these problems, and selected real-life applications of the models of interest.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Social Network Analysis
- Maximum Clique
- Greedy Randomize Adaptive Search Procedure
- Edge Density
- Greedy Heuristic
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
E. Aarts and J. Korst. Simulated Annealing and Boltzmann Machines. John Wiley & Sons Incorporated, Chichester, UK, 1989.
J. Abello, P.M. Pardalos, and M.G.C. Resende. On maximum clique problems in very large graphs. In J. Abello and J. Vitter, editors, External memory algorithms and visualization, volume 50 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pages 119–130. American Mathematical Society, 1999.
J. Abello, M.G.C. Resende, and S. Sudarsky. Massive quasi-clique detection. In S. Rajsbaum, editor, LATIN 2002: Theoretical Informatics, pages 598–612, London, 2002. Springer-Verlag.
R.D. Alba. A graph-theoretic definition of a sociometric clique. Journal of Mathematical Sociology, 3:113–126, 1973.
D. Applegate and D.S. Johnson. dfmax.c [c program, second dimacs implementation challenge]. ftp://dimacs.rutgers.edu/pub/challenge/graph/solvers/.
L. Babel. Finding maximum cliques in arbitrary and in special graphs. Computing, 46(4): 321–341, 1991.
E. Balas and J. Xue. Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring. Algorithmica, 15:397–412, 1996.
E. Balas and C. Yu. Finding a maximum clique in an arbitrary graph. SIAM Journal of Computing, 15:1054–1068, 1986.
B. Balasundram, S. Butenko, and I.V. Hicks. Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research, 59:133–142, 2011.
B. Balasundram, S. Butenko, and S. Trukhanov. Novel approaches for analyzing biological networks. Journal of Combinatorial Optimization, 10:23–29, 2005.
R. Battiti and M. Protasi. Reactive local search for the maximum clique problem. Technical report, Algorithmica, 2001.
N. Berry, T. Ko, T. Moy, J. Smrcka, J. Turnley, and B. Wu. Emergent clique formation in terrorist recruitment. The AAAI-04 Workshop on Agent Organizations: Theory and Practice, July 25, 2004, San Jose, California, 2004. Online: http://www.cs.uu.nl/ virginia/aotp/papers.htm.
M. Bhattacharyya and S. Bandyopadhyay. Mining the largest quasi-clique in human protein interactome. In IEEE International Conference on Artificial Intelligence Systems, pages 194–199, Los Alamitos, CA, USA, 2009. IEEE Computer Society.
V. Boginski. Network-based data mining: Operations research techniques and applications. In J. Cochran, editor, Encyclopedia of Operations Research and Management Science. Wiley, 2011.
V. Boginski, S. Butenko, and P. Pardalos. Network models of massive datasets. Computer Science and Information Systems, 1:79–93, 2004.
V. Boginski, S. Butenko, and P. Pardalos. Statistical analysis of financial networks. Computational Statistics & Data Analysis, 48:431–443, 2005.
V. Boginski, S. Butenko, and P. Pardalos. Mining market data: a network approach. Computers & Operations Research, 33:3171–3184, 2006.
I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo. The maximum clique problem. In D.-Z. Du and P. M. Pardalos, editors, Handbook of Combinatorial Optimization, pages 1–74, Dordrecht, The Netherlands, 1999. Kluwer Academic Publishers.
J.M. Bourjolly, G. Laporte, and G. Pesant. Heuristics for “nding k-clubs in an undirected graph. Computers and Operations Research, 27:559–569, 2000.
J.M. Bourjolly, G. Laporte, and G. Pesant. An exact algorithm for the maximum k-club problem in an undirected graph. European Journal of Operational Research, 138:21–28, 2002.
D. Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22: 251–256, 1979.
C. Bron and J. Kerbosch. Algorithm 457: Finding all cliques on an undirected graph. Communications of ACM, 16:575–577, 1973.
M. Brunato, H. Hoos, and R. Battiti. On effectively finding maximal quasi-cliques in graphs. In V. Maniezzo, R. Battiti, and J.P. Watson, editors, Proc. 2nd Learning and Intelligent Optimization Workshop, LION 2, volume 5313 of LNCS. Springer Verlag, 2008.
S. Butenko and W. Wilhelm. Clique-detection models in computational biochemistry and genomics. European Journal of Operational Research, 173:1–17, 2006.
R. Carraghan and P. Pardalos. An exact algorithm for the maximum clique problem. Operations Research Letters, 9:375–382, 1990.
M. Chams, A. Hertz, and A. de Werra. Some experiments with simulated annealing for coloring graphs. European Journal of Operational Research, 32:260–266, 1987.
H. Chen, W. Chung, J. J. Xu, G. Wang, Y. Qin, and M. Chau. Crime data mining: A general framework and some examples. Computer, 37(4):50–56, 2004.
Y. P. Chen, A. L. Liestman, and J. Liu. Clustering algorithms for ad hoc wireless networks. In Y. Pan and Y. Xiao, editors, Ad Hoc and Sensor Networks, Wireless Networks and Mobile Computing, pages 145–164. Nova Science Publishers, New York, 2005.
N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14:210–223, 1985.
D. J. Cook and L. B. Holder. Graph-based data mining. IEEE Intelligent Systems, 15(2):32–41, 2000.
R. H. Davis. Social network analysis: An aid in conspiracy investigations. FBI Law Enforcement Bulletin, 50(12):11–19, 1981.
A. H. Dekker. Social network analysis in military headquarters using CAVALIER. In Proceedings of Fifth International Command and Control Research and Technology Symposium, pages 24–26, Canberra, Australia, 2000.
R. Diestel. Graph Theory. Springer-Verlag, Berlin, 3 edition, 2006.
Dimacs. Cliques, Coloring, and Satisfiability: Second Dimacs Implementation Challenge. http://dimacs.rutgers.edu/Challenges/, 1995.
E. Durkheim. The Division of Labor in Society. Free Press, New York, [1893] 1984. Translated by W. D. Halls.
T. A. Feo and M. G. C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133, 1995.
T. A. Feo, M. G. C. Resende, and S. H. Smith. A greedy randomized adaptive search procedure for maximum independent set. Operations Research, 42:860–878, 1994.
I. Fischer and T. Meinl. Graph based molecular data mining - an overview. In W. Thissen, P. Wieringa, M. Pantic, and M. Ludema, editors, Proceedings of the 2004 IEEE International Conference on Systems, Man and Cybernetics, pages 4578–4582, Piscataway, NJ, 2004. IEEE.
M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.
M. Gendreau, P. Soriano, and L. Salvail. Solving the maximum clique problem using a tabu search approach. Ann. Oper. Res., 41:385–403, May 1993.
R. V. Gould. Multiple networks and mobilization in the paris commune, 1871. American Sociological Review, 56:716–729, 1991.
R. Hodson. Dignity at Work. Cambridge University Press, Cambridge, England, 2001.
S. Homer and M. Pinedo. Cliques, coloring, and satisfiability: Second DIMACS implementation challenge, chapter Experiments with polynomial-time clique approximation algorithms on very large graphs, pages 147–167. American Mathematical Society, 1996.
D. J. Johnson and M. A. Trick, editors. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. American Mathematical Society, Boston, MA, USA, 1996.
D.S. Johnson and C.R. Aragon. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256–278, 1974.
D.S. Johnson, C.R. Aragon, L.A. McGoech, and C. Shevon. Optimization by simulated annealing: An experimental evaluation; part ii, graph coloring and number partitioning. Operations Research, 39:378–406, 1991.
H.C. Johnston. Cliques of a graph – variations of Bron-Kerbosch algorithm. Int. J. Comput. Inf. Sci., 5:209–238, 1976.
R. Kopf and G. Ruhe. A computational study of the weighted independent set problem for general graphs. Foundations of Control Engineering, 12:167–180, 1987.
V. Krebs. Mapping networks of terrorist cells. Connections, 24:45–52, 2002.
P. Krishna, N. H. Vaidya, M. Chatterjee, and D. K. Pradhan. A cluster-based approach for routing in dynamic networks. ACM SIGCOMM Computer Communication Review, 27(2): 49–64, 1997.
E. Loukakis and C. Tsouros. A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically. Computing, 27:249–266, 1981.
R.D. Luce. Connectivity and generalized cliques in sociometric group structure. Psychometrika, 15:169–190, 1950.
R.D. Luce and A.D. Perry. A method of matrix analysis of group structure. Psychometrika, 14:95–116, 1949.
F. Mahdavi and B. Balasundaram. On inclusionwise maximal and maximum cardinality k-clubs in graphs. Preprint, 2010.
K. Makino and T. Uno. New algorithms for enumerating all maximal cliques. In Proc. Ninth Scandinavian Workshop Algorithm Theory (SWAT ’04), pages 260–272, 2004.
D. McAndrew. The structural analysis of criminal networks. In D. Canter and L. Alison, editors, The Social Psychology of Crime: Groups, Teams, and Networks, Offender Profiling Series, III, Aldershot, UK, 1999. Dartmouth.
B. McClosky and I. Hicks. Combinatorial algorithms for the maximum k-plex problem. Journal of Combinatorial Optimization, to appear.
G. A. Miller. WordNet, Princeton University. http://wordnet.princeton.edu, 2009.
R.J. Mokken. Cliques, clubs and clans. Quality and Quantity, 13:161–173, 1979.
J. Moody and D. R. White. Structural cohesion and embeddedness: A hierarchical concept of social groups. American Sociological Review, 68:103–127, 2003.
H. Moser, R. Niedermeier, and M. Sorge. Algorithms and experiments for clique relaxations - finding maximum s-plexes. In Proceedings of the 8th International Symposium on Experimental Algorithms, pages 233–244, 2009.
P. R. J. Östergård. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120:197–207, 2002.
J. Pattillo and S. Butenko. Clique, independent set, and graph coloring. In J. Cochran, editor, Encyclopedia of Operations Research and Management Science, pages 3150–3163. Wiley, 2011.
J. Pattillo, A. Veremyev, S. Butenko, and V. Boginski. On the maximum quasi-clique problem. Working paper.
P. Paxton. Is social capital declining in the united states? a multiple indicator assessment. American Journal of Sociology, 105:88–127, 1999.
F. J. Roethlisberger and W. J. Dickson. Management and the Worker. Harvard University Press, Cambridge, MA, 1939.
R. B. Rothenberg, J. J. Potterat, and D. E. Woodhouse. Personal risk taking and the spread of disease: Beyond core groups. Journal of Infectious Diseases, 174 (Supp. 2):S144–S149, 1996.
M. Sageman. Understanding Terrorist Networks. University of Pennsylvania Press, Philadelphia, PA, 2004.
R. J. Sampson and B. W. Groves. Community structure and crime: Testing social-disorganization theory. American Journal of Sociology, 94:774–802, 1989.
J. Scott. Social Network Analysis: A Handbook. Sage Publications, London, 2 edition, 2000.
S. B. Seidman. Network structure and minimum degree. Social Networks, 5:269–287, 1983.
S. B. Seidman and B. L. Foster. A graph theoretic generalization of the clique concept. Journal of Mathematical Sociology, 6:139–154, 1978.
E. C. Sewell. A branch and bound algorithm for the stability number of a sparse graph. INFORMS Journal on Computing, 10(4):438–447, 1998.
P. Soriano and M. Gendreau. Cliques, coloring, and satisfiability: Second DIMACS implementation challenge, chapter Tabu search algorithms for the maximum clique problem, pages 221–242. American Mathematical Society, 1996.
P. Soriano and M. Gendreau. Diversification strategies in tabu search algorithms for the maximum clique problem. Annals of Operations Research, 63:189–207, 1996.
I. Stojmenovic, editor. Handbook of Wireless Networks and Mobile Computing. Wiley InterScience, 2002.
L. Terveen, W. Hill, and B. Amento. Constructing, organizing, and visualizing collections of topically related, web resources. ACM Transactions on Computer-Human Interaction, 6:67–94, 1999.
E. Tomita and T. Kameda. An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. Journal of Global Optimization, 37(1):95–111, 2007.
E. Tomita, S. Mitsuma, and H. Takahashi. Two algorithms for finding a near-maximum clique. Technical report, UEC-TR-C1, 1988.
S. Trukhanov, B. Balasundaram, and S. Butenko. Exact algorithms for hard node deletion problems in graphs. Working paper, 2011.
A. Veremyev and V. Boginski. Identifying large robust network clusters via new compact formulations of maximum k-club problems. European Journal of Operational Research, in revision, 2010.
T. Washio and H. Motoda. State of the art of graph-based data mining. SIGKDD Explor. Newsl., 5(1):59–68, 2003.
S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, New York, 1994.
D. R. Wood. An algorithm for finding a maximum clique in a graph. Operations Research Letters, 21(5):211–217, 1997.
B. Wu and X. Pei. A parallel algorithm for enumerating all the maximal k-plexes. In J. G. Carbonell and J. Siekmann, editors, Emerging Technologies in Knowledge Discovery and Data Mining, Lecture Notes in Computer Science, chapter 47, pages 476–483. Springer, Berlin, Germany, 2007.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Pattillo, J., Youssef, N., Butenko, S. (2012). Clique Relaxation Models in Social Network Analysis. In: Thai, M., Pardalos, P. (eds) Handbook of Optimization in Complex Networks. Springer Optimization and Its Applications(), vol 58. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-0857-4_5
Download citation
DOI: https://doi.org/10.1007/978-1-4614-0857-4_5
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-0856-7
Online ISBN: 978-1-4614-0857-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)