Motif clustering and overlapping clustering for social network analysis

Pan Li, Hoang Dau, Gregory Puleo, Olgica Milenkovic

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

Abstract

Motivated by applications in social network community analysis, we introduce a new clustering paradigm termed motif clustering. Unlike classical clustering, motif clustering aims to minimize the number of clustering errors associated with both edges and certain higher order graph structures (motifs) that represent 'atomic units' of social organizations. Our contributions are two-fold: We first introduce motif correlation clustering, in which the goal is to agnostically partition the vertices of a weighted complete graph so that certain predetermined 'important' social subgraphs mostly lie within the same cluster, while 'less relevant' social subgraphs are allowed to lie across clusters. We then proceed to introduce the notion of motif covers, in which the goal is to cover the vertices of motifs via the smallest number of (near) cliques in the graph. Motif cover algorithms provide a natural solution for overlapping clustering and they also play an important role in latent feature inference of networks. For both motif correlation clustering and its extension introduced via the covering problem, we provide hardness results, algorithmic solutions and community detection results for two well-studied social networks.

Original languageEnglish (US)
Title of host publicationINFOCOM 2017 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509053360
DOIs
StatePublished - Oct 2 2017
Event2017 IEEE Conference on Computer Communications, INFOCOM 2017 - Atlanta, United States
Duration: May 1 2017May 4 2017

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

Other2017 IEEE Conference on Computer Communications, INFOCOM 2017
CountryUnited States
CityAtlanta
Period5/1/175/4/17

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Motif clustering and overlapping clustering for social network analysis'. Together they form a unique fingerprint.

  • Cite this

    Li, P., Dau, H., Puleo, G., & Milenkovic, O. (2017). Motif clustering and overlapping clustering for social network analysis. In INFOCOM 2017 - IEEE Conference on Computer Communications [8056956] (Proceedings - IEEE INFOCOM). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/INFOCOM.2017.8056956