PICS: Parameter-free identification of cohesive subgroups in large attributed graphs

Leman Akoglu, Hanghang Tong, Brendan Meeder, Christos Faloutsos

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

Abstract

Given a graph with node attributes, how can we find meaningful patterns such as clusters, bridges, and outliers? Attributed graphs appear in real world in the form of social networks with user interests, gene interaction networks with gene expression information, phone call networks with customer demographics, and many others. In effect, we want to group the nodes into clusters with similar connectivity and homogeneous attributes. Most existing graph clustering algorithms either consider only the connectivity structure of the graph and ignore the node attributes, or require several user-defined parameters such as the number of clusters. We propose PICS, a novel, parameter-free method for mining at- Tributed graphs. Two key advantages of our method are that (1) it requires no user-specified parameters such as the number of clusters and similarity functions, and (2) its running time scales linearly with total graph and attribute size. Our experiments show that PICS reveals meaningful and insightful patterns and outliers in both synthetic and real datasets, including call networks, political books, political blogs, and collections from Twitter and YouTube which have more than 70K nodes and 30K attributes.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th SIAM International Conference on Data Mining, SDM 2012
PublisherSociety for Industrial and Applied Mathematics Publications
Pages439-450
Number of pages12
ISBN (Print)9781611972320
DOIs
StatePublished - Jan 1 2012
Externally publishedYes
Event12th SIAM International Conference on Data Mining, SDM 2012 - Anaheim, CA, United States
Duration: Apr 26 2012Apr 28 2012

Publication series

NameProceedings of the 12th SIAM International Conference on Data Mining, SDM 2012

Other

Other12th SIAM International Conference on Data Mining, SDM 2012
CountryUnited States
CityAnaheim, CA
Period4/26/124/28/12

ASJC Scopus subject areas

  • Computer Science Applications

Fingerprint Dive into the research topics of 'PICS: Parameter-free identification of cohesive subgroups in large attributed graphs'. Together they form a unique fingerprint.

  • Cite this

    Akoglu, L., Tong, H., Meeder, B., & Faloutsos, C. (2012). PICS: Parameter-free identification of cohesive subgroups in large attributed graphs. In Proceedings of the 12th SIAM International Conference on Data Mining, SDM 2012 (pp. 439-450). (Proceedings of the 12th SIAM International Conference on Data Mining, SDM 2012). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611972825.38