Detecting hubs and quasi cliques in scale-free networks

Srihari, Sriganesh, Ng, Hoong Kee, Ning, Kang and Leong, Hon Wai (2008). Detecting hubs and quasi cliques in scale-free networks. In: Proceedings of the 19th International Conference On Pattern Recognition, Vols 1-6. 19th International Conference on Pattern Recognition (ICPR 2008), Tampa, FL, United States, (3274-3277). 8-11 December 2008. doi:10.1109/ICPR.2008.4761232


Author Srihari, Sriganesh
Ng, Hoong Kee
Ning, Kang
Leong, Hon Wai
Title of paper Detecting hubs and quasi cliques in scale-free networks
Conference name 19th International Conference on Pattern Recognition (ICPR 2008)
Conference location Tampa, FL, United States
Conference dates 8-11 December 2008
Proceedings title Proceedings of the 19th International Conference On Pattern Recognition, Vols 1-6   Check publisher's open access policy
Journal name 19th International Conference On Pattern Recognition, Vols 1-6   Check publisher's open access policy
Place of Publication Washington, DC, United States
Publisher IEEE Computer Society
Publication Year 2008
Sub-type Fully published paper
DOI 10.1109/ICPR.2008.4761232
ISBN 9781424421749
ISSN 1051-4651
Start page 3274
End page 3277
Total pages 4
Language eng
Abstract/Summary 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 high-degree 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.
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Conference Paper
Collection: Institute for Molecular Bioscience - Publications
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 21 Aug 2012, 11:12:11 EST by Susan Allen on behalf of Institute for Molecular Bioscience