|
Organizers |
Bipartite communities
by
Matthew Yancey
Institute for Defense Analysis / Center for Computing Science
A recent trend in data-mining is to find communities in a graph. Generally speaking, a community of a graph is a vertex set such that the number of edges contained entirely inside the set is "significantly more than expected." These communities are then used to describe families of proteins in protein-protein interaction networks, among other applications. Community detection is known to be NP-hard; there are several methods to find an approximate solution with rigorous bounds. In this talk we will discuss the spectral method to find communties with structure that is almost optimal.
We present a new goal in community detection: to find good bipartite communities. A bipartite community is a pair of disjoint vertex sets S, S' such that the number of edges with one endpoint in S and the other endpoint in S' is "significantly more than expected." We claim that this additional structure is natural to some applications of community detection. In fact, using other terminology, they have already been used in two different studies on distinct biological networks. We will show how the spectral methods for classical community detection can be generalized to finding bipartite communities. Additionally, we will present how the algorithm performs on public-source data sets.
Paper reference: arXiv:1412.5666
Date received: February 24, 2015
Copyright © 2015 by the author(s). The author(s) of this work and the organizers of the conference have granted their consent to include this abstract in Topology Atlas. Document # cbkp-12.