RDBMS as an Efficient Tool to Mine Cliques on Complex Networks

Authors

  • Ana Paula Appel Universidade Federal de São Carlos
  • Adriano Arantes Paterlini Universidade de São Paulo
  • Caetano Traina Jr. Universidade de São Paulo

DOI:

https://doi.org/10.5753/jidm.2010.1282

Keywords:

cliques, cluster coefficient, graph mining, power law, RDBMS

Abstract


Complex networks are intrinsically present in a wide range of applications.
Real world networks have several unique properties, such as, sparsity, node degree distribution, which follow a power law and a large amount of triangles that further form larger cliques.
Triangles and cluster coefficient, which are usually used to find groups, are not always enough to distinguish a different node neighborhood topology.
By using cliques of sizes 4 and 5, it is possible to study how triangles become involved to form large cliques.
To retrieve these cliques called k4 and k5 a novel technique called ``FCR - Fast Clique Retrieval'' has been developed, taking advantage of the data management and optimization techniques of a relational database management system and SQL to query cliques of sizes 4 and 5. This paper demonstrates that cliques (3, 4 and 5) follow interesting power laws that allow identifying nodes with suspicious behaviors. It also presents an extension of the cluster coefficient formula, which may become a valuable equation to identify nodes that most influence the network first eigenvalue.

Downloads

Download data is not yet available.

Downloads

Published

2010-10-06

How to Cite

Appel, A. P., Paterlini, A. A., & Traina Jr., C. (2010). RDBMS as an Efficient Tool to Mine Cliques on Complex Networks. Journal of Information and Data Management, 1(3), 407. https://doi.org/10.5753/jidm.2010.1282

Issue

Section

Regular Papers