Abstract:One of the most important problems in complex networks is to identify the influential vertices for understanding and controlling of information diffusion and disease spreading. Most of the current centrality algorithms focus on single feature or manually extract the attributes, which occasionally results in the failure to fully capture the vertex’s importance. A new vertex centrality approach based on symmetric nonnegative matrix factorization (SNMF), called VCSNMF, is proposed in this paper. For highlight the characteristics of a network,the adjacency matrix and the degree matrix are fused to represent original data of the network via a weighted linear combination. First, SNMF automatically extracts the latent characteristics of vertices by factorizing the established original data matrix. Then we prove that each vertex’s composite feature which is constructed with one-dimensional factor matrix can be approximated as the term of eigenvector associated with the spectral radius of the network, otherwise obtained by the factor matrix on the hyperspace. Finally, VCSNMF integrates the composite feature and the topological structure to evaluate the performance of vertices. To verify the effectiveness of the VCSNMF criterion, eight existing centrality approaches are used as comparison measures to rank influential vertices in ten real-world networks. The experimental results assert the superiority of the method.

Key words:complex networks, centrality, symmetric nonnegative matrix factorization (SNMF)

摘要：复杂网络中一个重要问题是确定有影响力的节点，主要用于理解和控制信息传播、疾病扩散等。目前的节点中心性算法主要关注单一的属性或者是手动提取属性，这导致节点全局重要性难以捕获。提出了基于对称非负矩阵分解（SNMF）的一个新的节点中性算法，称为VCSNMF。为了强调网络的属性，通过加权线性组合邻接矩阵和度矩阵来融合表示网络的初始数据。首先，对称非负矩阵分解通过分解初始数据矩阵来自动提取节点的潜在特征；然后，证明了每个节点的组合特征由网络的谱半径对应的特征向量得到的一维向量矩阵构成，或者是在超空间上的向量矩阵构成；最后，VCSNMF通过融合组合特征和网络拓扑特征来衡量节点的重要性。为了验证VCSNMF算法的有效性，在10个真实网络上，与已有的8个节点中心性算法进行了对比，实验结果验证了本算法的优越性。

关键词:复杂网络，中心性，对称非负矩阵分解