多层网络社区检测：联合非负矩阵分解新方法

168 浏览量更新于2024-08-28 1 收藏 940KB PDF 举报

"联合非负矩阵分解在多层网络中的社区检测" 本文主要探讨了如何在多层网络中有效地检测社区结构，这是一个复杂系统的典型特征。多层网络是由多个相互关联的子网络（或称为层）组成的，每个层代表特定类型的交互。现有的社区检测算法通常分为两类：一是将多层网络简化为单层网络处理，二是采用共识聚类方法扩展单层网络算法。然而，这两种方法都存在不足，它们未能充分利用各层间的关联信息，从而可能导致社区检测的精度下降。为了克服这些问题，作者提出了一个新的量化指标——多层模块密度（Multilayer Modularity Density），这一度量标准旨在更好地捕捉多层网络中的社区结构。文章进一步证明了优化多层模块密度的迹线等价于一系列常见的聚类算法的目标函数，如内核K均值、非负矩阵分解（Non-negative Matrix Factorization, NMF）、谱聚类以及多视图聚类。这一发现为设计适用于多层网络的社区检测算法提供了理论依据。在此基础上，研究者开发了一种新的半监督联合非负矩阵分解算法（Semi-supervised Joint Non-negative Matrix Factorization, S2-jNMF）。与传统的半监督方法不同，S2-jNMF将部分监督信息直接整合到其目标函数中，使得算法在处理带有部分标签数据的多层网络时能更准确地识别社区结构。这种算法能够同时分解与多层网络相关的矩阵，从而更好地捕获各层之间的相互作用。通过在模拟和真实世界网络上的大量实验，S2-jNMF算法的性能被验证明显优于现有用于多层网络社区检测的最新方法。这些实验结果表明，该方法在保留多层网络特性的同时，提高了社区检测的准确性和鲁棒性，为处理复杂多层网络问题提供了有力工具。该研究强调了多层网络社区检测的重要性，并提出了一种创新的解决方案，即利用联合非负矩阵分解来考虑各层间的联系，以提高社区检测的质量。这不仅丰富了网络分析的理论框架，也为实际应用中的社区发现提供了实用的算法。

1041-4347 (c) 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TKDE.2018.2832205, IEEE

Transactions on Knowledge and Data Engineering

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 3

increasing amount of attention because they can precisely

characterize and model systems in real world [24].

Community detection in networks has become a hot

topic since communities shed light on structure-function

relations, which has been extensively studied in the single-

layer networks. The most straightforward strategy is to ex-

tend the single-layer community detection algorithms to the

multi-layer networks to develop network-compression- and

consensus-based approaches. Network-compression-based

approaches compress multi-layer networks into a single-

layer network in which the single-layer community detec-

tion algorithms are adopted [31]. However, these methods

cannot preserve the community structure in multi-layer

networks, thereby leading to the low accuracy of algorithms

[25]. Thus, it is promising to extract community without

collapsing multi-layer networks. In this case, the single-

layer community detection algorithms are independently

applied to each layer, and then the communities at various

layers are combined to establish a consensus community

structure for multi-layer networks. However, this strategy

is also criticized for ignoring the connection among various

layers.

Thus, there is a critical need to develop effective algo-

rithms for community detection in multi-layer networks,

rather than by simply extending the available single-layer

network algorithms. To identify communities in multi-layer

networks, we must simultaneously take into account multi-

ple layers during the community search procedure. The ﬁrst

step in multi-layer community detection is to quantify the

community in multi-layer networks. Ma et al. [29] quantiﬁed

the connectivity of communities in multi-layer networks

using information entropy and transformed the community

detection in multi-layer networks into an entropy optimiza-

tion problem. They also proposed a greedy-search-based

algorithm (M-Module) for multi-layer community detection.

Didier et al. [40] quantiﬁed communities by extending the

modularity function to detect communities from multi-layer

networks and developed the (MolTi) algorithm for multi-

layer communities. Some alternatives based on random

network models are also available for the quantiﬁcation

of multi-layer communities [41], [42]. The successful ap-

plication of these algorithms highlights the need for the

integrative analysis of multiple layers, which is also one of

the major motivations of this study.

In other words, the layers of networks can be consid-

ered as different views of data, which provide information

complementary to each other. To integrate information from

multiple views, multi-view clustering algorithms cluster

multiple views simultaneously to derive a solution that

uncovers the common latent structure shared by multiple

views. Many multi-view clustering algorithms has been

widely developed [33]–[39]. Existing multi-view clustering

methods can be roughly categorized into two classes: loss-

function and subspace-based approaches. The algorithms in

the ﬁrst category incorporate multiple views into the cluster-

ing process by optimizing the predeﬁned loss functions [33],

[38], while the subspace-based algorithms project multiple

views into a common lower dimensional subspace where

communities are discovered [35]. For example, to explore

the information in each view, Kumar et al. [38] developed

the multi-view spectral clustering MVspec algorithm, where

a clustering solution is derived from each individual view

and then all the solutions are fused based on consensus.

However, MVspec is criticized for the independence of

features from various views. To solve this problem, Han

et al. [39] proposed MVnmf by formulating a joint matrix

factorization process with the constraint that pushes the

clustering solution of each view toward a common consen-

sus instead of ﬁxing such solution directly.

Even though great efforts have been devoted to commu-

nity detection in multi-layer networks, few attempt has been

made to draw the relation among various algorithms. In the

forthcoming sections, we address the equivalence relation

among algorithms.

TABLE 1

Main Symbols

Symbol Deﬁnition and Description

G graph with vertex set V and edge set E

G multi-layer network {G

[1]

, . . . , G

[m]

}

[l]

the weighted adjacency matrix for G

[l]

degree diagonal matrix D

[l]

= diag(d

[l]

, . . . , d

[l]

)

W adjacency matrix = {W

[1]

, . . . , W

[m]

}

the element at i-th row jth column in matrix W

the i-th row of matrix W

the j-th column of matrix W

X the indication matrix for V , where x

if v

belongs to cluster C

, 0 otherwise

′

the transpose of matrix X

X column normalized matrix X, i.e. x

√

′

l the index for the layers of network l ∈ {1, . . . , m}

}

c=1

the communities for G

({C

}

i=1

) multi-layer modularity density for communities

}

i=1

) in G (Q

for short)

trace(W ) the trace of matrix W , i.e. trace(W ) =

∑

3 MULTI-LAYER MODULARITY DENSITY

Before giving a detailed description of multi-layer modular-

ity density, we introduce some terminologies that are widely

used in the forthcoming sections.

Given an undirected and unweighted network G =

(V, E) with vertex set V = {v

, v

, . . . , v

} (n is the number

of vertices in G, i.e., n = |V |) and edge set E = {(v

, v

)},

the adjacency matrix A = (a

) is constructed whose ele-

ment is a

= 1 if there is an edge between vertex v

and

, 0 otherwise. The degree of vertex v

is deﬁned as the

number of neighbors in the network, i.e., d



. If

G is weighted, the weighted adjacency matrix is denoted

by W = (w

), where element w

is the weight on edge

, v

). The weighted degree of vertex v

is the sum of

weight on edge connecting to v

, i.e., d



. For a pair

of subsets V

and V

of V , let L(V

, V

) =



i∈V

,j∈V

and V

= V \ V

Let {V

}

c=1

be a hard partitioning of G (i.e. V

∩ V

= ∅



, and

∪

), where

is the set of vertices in the

c-th community and k is the number of communities. The

modularity density Q

for {V

}

c=1

is deﬁned as [10]

({V

}

c=1

) =



c=1

L(V

, V

) − L(V

, V

)

. (1)

剩余13页未读，继续阅读

weixin_38727980

粉丝: 3
资源: 931

多层网络社区检测：联合非负矩阵分解新方法

MultiTensor:多层网络张量分解，用于社区检测，链路预测和测量层相互依赖

成对约束对称非负矩阵分解的社区检测

使用多层边缘混合模型进行社区检测

非负矩阵分解matlab代码-nmf-ml:多层非负矩阵分解MATLAB实现

近似稀疏约束的多层非负矩阵分解高光谱解混

nmf代码.zip_cnn中的nmf_nmf_改进NMF_非负矩阵_非负矩阵分解

mlnmf-matlab_matlab_高光谱解混_多层非负矩阵分解_

MATLAB多层非负矩阵分解实战项目案例解析

高光谱图像解混：MATLAB实现多层非负矩阵分解

非负矩阵分解 的matlab实现

最新资源

非负矩阵分解的matlab实现