Article

An Algorithm to Discover the k-Clique Cover in Networks

Authors:

Armando B. Mendes,

Jorge M. SantosAuthors Info & Claims

EPIA '09: Proceedings of the 14th Portuguese Conference on Artificial Intelligence: Progress in Artificial Intelligence

Pages 363 - 373

https://doi.org/10.1007/978-3-642-04686-5_30

Published: 07 October 2009 Publication History

Abstract

In social network analysis, a k-clique is a relaxed clique, i.e., a k-clique is a quasi-complete sub-graph. A k-clique in a graph is a sub-graph where the distance between any two vertices is no greater than k. The visualization of a small number of vertices can be easily performed in a graph. However, when the number of vertices and edges increases the visualization becomes incomprehensible. In this paper, we propose a new graph mining approach based on k-cliques. The concept of relaxed clique is extended to the whole graph, to achieve a general view, by covering the network with k-cliques. The sequence of k-clique covers is presented, combining small world concepts with community structure components. Computational results and examples are presented.

References

[1]

Alba, R.D.: A graph-theoretic definition of a sociometric clique. Journal of Mathematical Sociology 3, 113-126 (1973).

[2]

Berners-Lee, T.: The Next Wave of the Web: Plenary Panel. In: 15th International World Wide Web Conference, WWW2006, Edinburgh, Scotland (2006).

[3]

Cavique, L., Luz, C.: A Heuristic for the Stability Number of a Graph based on Convex Quadratic Programming and Tabu Search, special issue of the Journal of Mathematical Sciences, Aveiro Seminar on Control Optimization and Graph Theory, Second Series (to appear, 2009).

[4]

Cavique, L., Rego, C., Themido, I.: A Scatter Search Algorithm for the Maximum Clique Problem. In: Ribeiro, C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 227- 244. Kluwer Academic Publishers, Dordrecht (2002).

[5]

Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 233-235 (1979).

[6]

Cook, D.J., Holder, L.B. (eds.): Mining Graph Data. John Wiley & Sons, New Jersey (2007).

[7]

DIMACS: Maximum clique, graph coloring, and satisfiability, Second DIMACS implementation challenge (1995), http://dimacs.rutgers.edu/Challenges/ (accessed April 2009).

[8]

Erdos, P., Renyi, A.: On Random Graphs. I. Publicationes Mathematicae 6, 290-297 (1959).

[9]

Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the Internet topology. In: SIGCOMM, pp. 251-262 (1999).

[10]

Floyd, R.W.: Algorithm 97: Shortest Path. Communications of the ACM 5(6), 345 (1962).

[11]

Gomes, M., Cavique, L., Themido, I.: The Crew Time Tabling Problem: an extension of the Crew Scheduling Problem. Annals of Operations Research, volume Optimization in transportation 144(1), 111-132 (2006).

[12]

Grossman, J., Ion, P., Castro, R.D.: The Erdos number Project (2007), http://www.oakland.edu/enp/ (accessed April 2009).

[13]

Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Science 9, 256-278 (1974).

[14]

Kellerman, E.: Determination of keyword conflict. IBM Technical Disclosure Bulletin 16(2), 544-546 (1973).

[15]

Luce, R.D.: Connectivity and generalized cliques in sociometric group structure. Psychometrika 15, 159-190 (1950).

[16]

Milgram, S.: The Small World Problem. Psychology Today 1(1), 60-67 (1967).

[17]

Mokken, R.J.: Cliques, clubs and clans. Quality and Quantity 13, 161-173 (1979).

[18]

Moreno, J.L.: Who Shall Survive? Nervous and Mental Disease Publishing Company, Washington DC (1934).

[19]

Scott, J.: Social Network Analysis - A Handbook. Sage Publications, London (2000).

[20]

Soriano, P., Gendreau, M.: Tabu search algorithms for the maximum clique. In: Johnson, D.S., Trick, M.A. (eds.) Clique, Coloring and Satisfiability, Second Implementation Challenge DIMACS, pp. 221-242 (1996).

[21]

Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge (1994).

[22]

Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393(6684), 409-410 (1998).

Cited By

Taha KYoo P(2015)A System for Analyzing Criminal Social NetworksProceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 201510.1145/2808797.2808827(1017-1023)Online publication date: 25-Aug-2015
https://dl.acm.org/doi/10.1145/2808797.2808827
Cavique LMarques NSantos J(2014)An Algorithm to Condense Social Networks and Identify BrokersAdvances in Artificial Intelligence -- IBERAMIA 201410.1007/978-3-319-12027-0_27(331-343)Online publication date: 24-Nov-2014
https://dl.acm.org/doi/10.1007/978-3-319-12027-0_27
Gutiérrez YVázquez SMontoyo A(2012)A graph-based approach to WSD using relevant semantic trees and n-cliques modelProceedings of the 13th international conference on Computational Linguistics and Intelligent Text Processing - Volume Part I10.1007/978-3-642-28604-9_19(225-237)Online publication date: 11-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28604-9_19
Show More Cited By

An Algorithm to Discover the k-Clique Cover in Networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

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 the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph $$G=(V,E)$$G=(V,E), the complete width of G is the minimum k such that there exist k independent sets $$\mathtt {N}_i\subseteq V$$Ni⊆V, $$1\le i\le k$$1≤i≤k, such that ...
The K-clique Densest Subgraph Problem
WWW '15: Proceedings of the 24th International Conference on World Wide Web

Numerous graph mining applications rely on detecting subgraphs which are large near-cliques. Since formulations that are geared towards finding large near-cliques are hard and frequently inapproximable due to connections with the Maximum Clique problem, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EPIA '09: Proceedings of the 14th Portuguese Conference on Artificial Intelligence: Progress in Artificial Intelligence

October 2009

655 pages

ISBN:9783642046858

Editors:
Luís Seabra Lopes
IEETA/Department of Electronics & Telecommunication, University of Aveiro, Aveiro, Portugal 3810-153
,
Nuno Lau
LSE-IEETA/DETI, Universidade de Aveiro, Portugal
,
Pedro Mariano
Universidade de Aveiro, Aveiro, Portugal
,
Luís M. Rocha
School of Informatics, Indiana University, Bloomington, IN, USA, and Computational Biology Collaboratorium, Instituto ulbenkian da Ciencia, Portugal

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 October 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Taha KYoo P(2015)A System for Analyzing Criminal Social NetworksProceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 201510.1145/2808797.2808827(1017-1023)Online publication date: 25-Aug-2015
https://dl.acm.org/doi/10.1145/2808797.2808827
Cavique LMarques NSantos J(2014)An Algorithm to Condense Social Networks and Identify BrokersAdvances in Artificial Intelligence -- IBERAMIA 201410.1007/978-3-319-12027-0_27(331-343)Online publication date: 24-Nov-2014
https://dl.acm.org/doi/10.1007/978-3-319-12027-0_27
Gutiérrez YVázquez SMontoyo A(2012)A graph-based approach to WSD using relevant semantic trees and n-cliques modelProceedings of the 13th international conference on Computational Linguistics and Intelligent Text Processing - Volume Part I10.1007/978-3-642-28604-9_19(225-237)Online publication date: 11-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28604-9_19
Gutiérrez YVázquez SMontoyo A(2011)Word sense disambiguationProceedings of the 16th international conference on Natural language processing and information systems10.5555/2026011.2026023(112-124)Online publication date: 28-Jun-2011
https://dl.acm.org/doi/10.5555/2026011.2026023
Gutiérrez YFernàndez AMontoyo AVázquez SErk KStrapparava C(2010)UMCC-DLSI: Integrative resource for disambiguation taskProceedings of the 5th International Workshop on Semantic Evaluation10.5555/1859664.1859759(427-432)Online publication date: 15-Jul-2010
https://dl.acm.org/doi/10.5555/1859664.1859759

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents