Soft unveiling of communities via egonet tensors
Soft unveiling of communities via egonet tensors
复制标题
DOI：
10.1109/acssc.2017.8335494
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Fatemeh Sheikholeslami;G. Giannakis
中科院分区：
文献类型：
--
作者：
Fatemeh Sheikholeslami;G. Giannakis
网络上社区检测的任务涉及识别底层节点组，这些节点的隐藏关联表现为成员之间的密集连接和稀疏的社区间链接。目前的工作旨在通过张量分析捕获多跳连接模式来提高传统基于矩阵的社区检测算法的鲁棒性。为此，本文提出了一种新颖的基于张量的网络表示，并将社区检测任务转化为受约束的 PARAFAC 分解。随后，通过交替最小二乘法处理所提出的三线性最小化，其中使用乘子交替方向法（ADMM）解决中间子问题以确保收敛。该框架进一步扩展以适应时变图，其中边集以及底层社区随着时间的推移而演变。数值测试证实了通过新颖的表示以及所提出的张量分解提供的增强的鲁棒性。
The task of community detection over a network pertains to identifying the underlying groups of nodes whose often-hidden association has manifested itself in dense connections among the members, and sparse inter-community links. The present work aims at improving the robustness of the traditional matrix-based community detection algorithms via capturing multi-hop connectivity patterns through tensor analysis. To this end, a novel tensor-based network representation is advocated in this contribution, and the task of community detection is cast as a constrained PARAFAC decomposition. Subsequently, the proposed tri-linear minimization is handled via alternating least-squares, where intermediate subproblems are solved using the alternating direction method of multipliers (ADMM) to ensure convergence. The framework is further broadened to accommodate time-varying graphs, where the edgeset as well as the underlying communities evolve through time. Numerical tests corroborate the increased robustness provided through the novel representation as well as the proposed tensor decomposition.