Latent Network Features and Overlapping Community Discovery via Boolean Intersection Representations

Research output: Contribution to journalArticle

Abstract

We propose a new latent Boolean feature model for complex networks that capture different types of node interactions and network communities. The model is based on a new concept in graph theory, termed the Boolean intersection representation of a graph, which generalizes the notion of an intersection representation. We mostly focus on one form of Boolean intersection, termed cointersection, and describe how to use this representation to deduce node feature sets and their communities. We derive several general bounds on the minimum number of features used in cointersection representations and discuss graph families for which exact cointersection characterizations are possible. Our results also include algorithms for finding optimal and approximate cointersection representations of a graph.

Original languageEnglish (US)
Article number8004484
Pages (from-to)3219-3234
Number of pages16
JournalIEEE/ACM Transactions on Networking
Volume25
Issue number5
DOIs
StatePublished - Oct 2017

Keywords

  • Boolean functions
  • clustering algorithms
  • network theory

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Latent Network Features and Overlapping Community Discovery via Boolean Intersection Representations'. Together they form a unique fingerprint.

  • Cite this