Latent Network Features and Overlapping Community Discovery via Boolean Intersection Representations

Son Hoang Dau, Olgica Milenković

Abstract

We propose a new latent Boolean feature model for complex networks that captures 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.

Introduction: Beyond the Clique

In network analysis, we often explain connections by looking for "latent features"—hidden attributes like shared hobbies or professional affiliations. Traditional combinatorial models, such as standard intersection graphs, assume two nodes are connected if they share at least one common feature.

Standard intersection representation where edges are formed by sharing a single feature from a set.

While elegant, this "OR" logic is restrictive: it implies that every community must be a "clique" where every member is connected to every other member. Real-world interactions are more nuanced; you might only connect with someone if you share a professional interest and live in the same city. This paper introduces Boolean intersection representations, a framework that uses multi-conditional logic to capture these complex interactions and the overlapping communities they form.

The Cointersection Model

The authors generalize the standard intersection model using Boolean functions, focusing primarily on the cointersection model which utilizes "AND" logic. In this model, two nodes $u$ and $v$ are connected if and only if they share at least one feature from set $A$ AND at least one feature from set $B$.

A cointersection representation demonstrating how overlapping communities (sets $a_i$ and $b_j$) interact to form edges via "AND" logic.

This shift from "OR" to "AND" allows features to define communities that are not necessarily cliques. An edge only appears at the intersection of two different types of communities, providing a much more realistic representation of social and biological clusters.

Methods and Algorithms

The paper employs several rigorous approaches to explore this new representation:

  • Theoretical Bounds: Using probabilistic methods like the Lovász Local Lemma, the authors prove upper bounds on the "cointersection number"—the minimum number of features needed. For a graph with $n$ vertices and max degree $d$, they established that $\theta^c(G) \le 16d^{5/2}\sqrt{n}$.
  • Exact Algorithms: The problem is mapped to a Boolean Satisfiability (SAT) instance, allowing off-the-shelf solvers to find optimal feature assignments for smaller graphs.
  • Approximate Algorithms: For larger networks, a Simulated Annealing algorithm is used to maximize the "match score" between the model and observed edges.

Key Results and Insights

  • Efficiency: The cointersection number $\theta^c(G)$ is often significantly smaller than the standard intersection number. For any graph $G$, $\theta^c(G) \le 1 + \theta_1(G)$.
  • Geometric Connections: The research uncovers a link between optimal graph representations and finite geometry, showing that efficient representations for certain multipartite graphs are equivalent to finding affine planes.
  • Real-World Application: Using the classic Zachary’s Karate Club benchmark, the simulated annealing algorithm (with only 4 total features) perfectly recovered the famous faction split and identified overlapping sub-communities that provided deeper insight into the network's structure than simple binary clustering.

Conclusion and Future Work

Boolean intersection representations offer a flexible framework for modeling network connectivity that moves beyond simple cliques. While determining the exact cointersection number is NP-complete, the proposed approximate algorithms show great promise for real-world discovery. Future work will explore more complex Boolean functions in Disjunctive Normal Form (DNF) and apply the model to biological datasets, such as protein-protein interaction networks, where multi-conditional logic is prevalent.

Summary updated

Abstract

We propose a new latent Boolean feature model for complex networks that captures 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.
BibTeX
@inproceedings{dau2017latent,
  author = {Son Hoang Dau and Olgica Milenković},
  title = {{Latent Network Features and Overlapping Community Discovery via Boolean Intersection Representations}},
  booktitle = {IEEE/ACM},
  year = {2017},
  doi = {10.1109/tnet.2017.2728638},
}
Figure