Detecting hubs and quasi cliques in scale-free networks

Sriganesh Srihari, Hoong Kee Ng, Kang Ning, Hon Wai Leong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

Scale-free networks are believed to closely model most real-world networks. An interesting property of such networks is the existence of so-called hub and community structures. In this paper, we model hubs as highdegree nodes and communities as quasi cliques. We propose a new problem formulation called the λ-LIST DOMINATING SET and show how this single problem is suited to model both the structures in real-world networks better than traditional problems like VERTEX COVER and CLIQUE. Additionally, we provide a fixed-parameter tractable algorithm to this detect these structures and show experimental results on Protein-Protein Interaction networks.

Original languageEnglish
Title of host publication2008 19th International Conference on Pattern Recognition, ICPR 2008
Publication statusPublished - 1 Dec 2008
Event2008 19th International Conference on Pattern Recognition, ICPR 2008 - Tampa, FL, United States
Duration: 8 Dec 200811 Dec 2008

Other

Other2008 19th International Conference on Pattern Recognition, ICPR 2008
CountryUnited States
CityTampa, FL
Period8/12/0811/12/08

ASJC Scopus subject areas

  • Computer Vision and Pattern Recognition

Cite this

Srihari, S., Ng, H. K., Ning, K., & Leong, H. W. (2008). Detecting hubs and quasi cliques in scale-free networks. In 2008 19th International Conference on Pattern Recognition, ICPR 2008 [4761232]