基于非负矩阵分解的社交网络社团发现方法

    徐晟+赵永刚

    

    摘要：社交网络用户众多，连接关系复杂，挖掘其中的社团结构对于研究网络的结构，分析用户行为特点，揭示信息传播规律都有重要的意义。本文针对有向加权和无向加权网络特点，介绍了基于非负矩阵分解的社团划分算法。真实数据集上的实验表明，算法是有效的，符合人们对网络中人际关系的直观理解，为研究社交网络的结构和关系演变提供了一种有效的方法。

    关键词： 社交网络； 社团结构；非负矩阵分解

    中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）12-0049-02

    1 概述

    社交网络如微博、微信、博客等在人们的生活中发挥的越来越广泛的应用，这些社交网络也在网络舆情等方面发挥了重要作用。这是因为在社交网络中，用户之间相互连接、影响，从而促进了信息像洪水一样的快速而广泛的传播，与传统媒体、门户网站不同之处就在于，他没有一个明显的传播主渠道。在社交网络中，用户经常只是和少部分其他用户信息交互频繁，而与其他大部分用户联系很少，这样，在用户之间就形成了许多明显的圈子，即社团结构。社团内的用户之间相互联系密切，相互共享信息或者进行合作，如微博、facebook、Twitter等网络应用中，有共同兴趣的节点相互分享视频、评论等信息，形成一种社团结构[1]。在这些圈子内，总会存在诸如名人、超级用户（如微博中的大V）和活跃用户，是社团中的活跃分子。相比之下，用户与社团外部之间的联系就相对稀疏的许多，但是，许多舆情也通过这些稀疏的连接将信息从一个社团散布到其他社团，从而引起其他社团广泛的关注。因此，在社交网络上，既要挖掘这些社团结构，获得用户之间的关系结构，便于对网络进行管理，又要掌握网络中社团活动的重要用户，掌握信息广泛传播的关键节点，只有这样，才可以全面掌握社交网络的活动规律，正确预见潜在的网络事件，挖掘诸如犯罪关系网等重要信息，保障网络的健康有序。

    社交网络是一种复杂网络，它规模庞大，结构复杂，表现在节点数目巨大，网络结构呈现多种不同特征。连接具有多样性，节点之间的连接权重存在诧异。节点集可能属于非线性动力学系统，例如节点状态随时间发生复杂变化。自2002年Girven和Newman提出社区挖掘的概念至今，新的理论、方法层出不穷，新的应用领域不断涌现.它不仅吸引了来自计算机科学、物理、数学、生物和社会学等领域的研究者，成为最具挑战性的多学科交叉研究课题之一；而且已被应用于社会网络分析，如恐怖组织识别、组织结构管理、网络推荐等方方面面。采用非负矩阵分解（NMF）的方法进行社团的发现。

    2 基于非负矩阵分解的社团发现的方法

    非负矩阵分解是近年来出现的一种新方法。它对矩阵分解中的元素都添加了非负的限制，即大于或等于0，这与事物的整体是部分之和的直观概念相符合，在应用中具有很强的可解释性，但是，对于非对称矩阵的非负分解，目前的算法效果并不太好，而在实际中，很多网络连接关系是有向的，它们对应的矩阵就是非对称的。我们通过对目标矩阵进行简单变换，添加必要的约束项，来实现基于非负矩阵分解的有向加权网络的社团发现，同时进一步分析用户在社团中的重要性，判断用户在社团中所处的作用和特点，从而可以达到有效分析和解剖网络结构的目的。

    2.1社团发现模型

    对于一个网络连接关系，一般使用图来描述。其中：表示第i个节点，表示第i个节点到第j个节点关系的大小。其中， X是社团指示矩阵 ，其元素表示第i个节点属于第j个社团的大小。 S是社团关系矩阵 ，其元素表示第i个社团与第j个社团的密切程度，n 表示节点的个数，k表示社团的个数，一般来讲，社团的个数要远远小于节点的个数。

    3 实验

    3.1 Zachary karate数据集

    Zachary karate数据集是一个真实网。它是Zachary空手道俱乐部成员关系网络，是社会学分析等领域中最常用的一个小型检测网络之一。从1970到1972年，Wayne Zachary用三年时间观察了美国一所大学空手道俱乐部成员间的社会关系，并构造出了社会关系网（Zacharys karate club network）。网络中的每个节点分别表示某一个俱乐部成员，节点间的连接表示两个成员经常一起出现在俱乐部活动（如空手道训练、俱乐部聚会等）之外的其他场合，即在俱乐部之外他们可以被称为朋友。调查过程中，该俱乐部因为主管John A.（节点34）与教练Mr. Hi（节点1）之间的争执而分裂成2个各自为核心的小俱乐部。这个矩阵经常被用来检测算法的有效性。

    3.2 其他真实数据集

    我们还利用其他真实数据集来做实验比较，如：American College Football，Neural Network数据集，以模块度值[11]作为衡量指标，实验表明，我们的算法都得到了较精确的社团划分结果。除了Dolphin Social Network数据集外，我们的算法都要好于其他基于非负矩阵分解的算法。

    4 结论

    本文针对网络中节点复杂的连接关系，改进了以往社团划分算法只能解决无向网络问题的缺点，构建了基于有向加权图的非负矩阵社团划分模型，提出了模型求解的算法，并且提出了社团中节点的重要性等性质的定量分析，在真实的网络数据集上的实验表明，我们提出的算法正确的给出了社团划分结果，并对节点在社团中的性质进行了详细的分析，其结果符合人们的直观认识。我们的算法对于研究社交网络中复杂的人际关系提供了一种有用的方法，对于网络的结构分析，信息在用户之间的传播有参考意义。

    参考文献：

    [1] 曹贵强.纸币识别及红外鉴伪技术的研究[D].辽宁科技大学，2014.

    [2] 李玉翔.基于网络社区的用户兴趣建模与推荐技术研究[D].解放军信息工程大学，2013.