Detection of overlapping communities in real-world networks is a generally challenging task. Upon recognizing that a network is in fact the union of its egonets, a novel network representation using multiway data structures is advocated in this contribution. The introduced sparse tensor-based representation exhibits richer structure compared to its matrix counterpart and, thus, enables a more robust approach to community detection. To leverage this structure, a constrained tensor approximation framework is introduced using PARAFAC decomposition. The arising constrained trilinear optimization is handled via alternating minimization, where intermediate subproblems are solved using the alternating direction method of multipliers to ensure convergence. The factors obtained provide soft community memberships, which can further be exploited for crisp, and possibly-overlapping community assignments. The framework is further broadened to include time-varying graphs, where the edgeset as well as the underlying communities evolve through time. The performance of the proposed approach is assessed via tests on benchmark synthetic graphs as well as real-world networks. As corroborated by numerical tests, the proposed tensor-based representation captures multihop nodal connections, that is, connectivity patterns within single-hop neighbors, whose exploitation yields a more robust community identification in the presence of mixing as well as overlapping communities.
Bibliographical noteFunding Information:
Manuscript received July 13, 2017; revised February 19, 2018, May 11, 2018, and September 10, 2018; accepted September 11, 2018. Date of publication September 24, 2018; date of current version October 1, 2018. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Pierre Borgnat. This work was supported by the National Science Foundation under Grants 1500713, 1442686, and 1711471. (Corresponding author: Georgios B. Giannakis.) The authors are with the Department of Electrical and Computer Engineering and Digital Technology Center, University of Minnesota, Minneapolis, MN 55455 USA (e-mail:,email@example.com; firstname.lastname@example.org).
- Community detection
- constrained PARAFAC
- egonet subgraphs
- overlapping communities
- sparse tensors
- tensor decomposition