Bipartite communities via spectral partitioning

Kelly B. Yancey () and Matthew P. Yancey ()
Additional contact information
Kelly B. Yancey: University of Maryland
Matthew P. Yancey: Institute for Defense Analyses/Center for Computing Sciences (IDA/CCS)

Journal of Combinatorial Optimization, No 0, 34 pages

Abstract: Abstract In this paper we are interested in finding communities with bipartite structure. A bipartite community is a pair of disjoint vertex sets S, $$S'$$S′ such that the number of edges with one endpoint in S and the other endpoint in $$S'$$S′ is “significantly more than expected.” This additional structure is natural to some applications of community detection. In fact, using other terminology, they have already been used to study correlation networks, social networks, and two distinct biological networks. In 2012 two groups independently [(1) Lee, Oveis Gharan, and Trevisan and (2) Louis, Raghavendra, Tetali, and Vempala] used higher eigenvalues of the normalized Laplacian to find an approximate solution to the k-sparse-cuts problem. In 2015 Liu generalized spectral methods for finding k communities to find k bipartite communities. Our approach improves the bounds on bipartite conductance (measure of strength of a bipartite community) found by Liu and also implies improvements to the original spectral methods by Lee et al. and Louis et al. We also highlight experimental results found when applying a practical algorithm derived from our theoretical results to three distinct real-world networks.

Keywords: Community detection; Spectral graph theory; Network analysis (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00574-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00574-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00574-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().