Mining the Largest Dense Vertexlet in a Weighted Scale-free Graph

Article type: Research Article

Authors: Bandyopadhyay, Sanghamitra | Bhattacharyya, Malay

Affiliations: Machine Intelligence Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata - 700108, India. E-mail: {sanghami,malay_r}@isical.ac.in

Abstract: An important problem of knowledge discovery that has recently evolved in various reallife networks is identifying the largest set of vertices that are functionally associated. The topology of many real-life networks shows scale-freeness, where the vertices of the underlying graph follow a power-law degree distribution. Moreover, the graphs corresponding to most of the real-life networks are weighted in nature. In this article, the problem of finding the largest group or association of vertices that are dense (denoted as dense vertexlet) in a weighted scale-free graph is addressed. Density quantifies the degree of similarity within a group of vertices in a graph. The density of a vertexlet is defined in a novel way that ensures significant participation of all the vertices within the vertexlet. It is established that the problem is NP-complete in nature. An upper bound on the order of the largest dense vertexlet of a weighted graph, with respect to certain density threshold value, is also derived. Finally, an O(n^2 log n) (n denotes the number of vertices in the graph) heuristic graph mining algorithm that produces an approximate solution for the problem is presented.

Keywords: Graphs and networks, scale-free, mining methods and algorithms, knowledge discovery, bioinformatics

DOI: 10.3233/FI-2009-164

Journal: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 1-25, 2009