K-means型社区发现方法研究

发布时间：2019-11-12 13:50

【摘要】：随着信息技术的飞速发展,Twitter、Facebook、新浪微博、微信等各类在线社交平台逐渐改变人们的生活和工作方式。在这些平台上,每天产生大量、繁杂的网络数据,包括节点链接关系数据和内容属性数据。链接关系数据隐含网络统计特性、潜在结构和交互规律,内容属性数据包含丰富的数字图像、文本和音频等描述节点特征属性的内容信息。对这些复杂的网络数据进行挖掘和分析为机器学习、数据挖掘等领域提供了新的机遇和挑战。网络的社区发现是进行网络分析的一个基本问题,这对实现数据的自然划分、数据压缩、可视化分析、以及内容推荐等具有重要的科学意义和应用价值。该问题提出以来,各种社区发现方法和技术应运而生,其中,K-means聚类算法由于其思想简单、易于实现、对大规模数据的处理具有高效性和可伸缩性等,在网络数据的节点划分中得到广泛应用。但该算法也存在明显的缺陷:1)对初始点的选取十分敏感,其性能容易受初始种子节点的影响;2)要求预先指定聚类个数。因此,针对网络型数据的特性,如何提出K-means型划分聚类方法的初始化策略有待进一步研究。研究发现,实际网络通常稀疏而且存在噪声信息,对于社区结构不清晰的网络,如何利用网络中辅助信息挖掘有意义的社区结构为研究者提出新的要求。本文以网络数据为研究对象,对K-means型划分聚类方法中的聚类个数、初始点选取、如何有效处理社区结构不清晰网络以及将节点的属性特征进行有效结合展开研究,并对如何考虑边的不确定性进行探索。本文的主要研究成果包括:1)提出了一种基于节点中心度和离散度的社区发现方法。根据网络数据的特性,基于网络中节点的中心度和离散度两个量化指标,从决策图和综合得分两个角度给出确定聚类个数和初始中心选择的策略,为基于K-means型方法进行网络的社区发现提供一定的指导,人工网络和实际网络上的对比实验验证了提出方法的有效性。在该方法基础上,提出了一种通过节点属性的k近邻图(k Nearest Neighbor, kkNN)增强的社区发现方法,通过节点的属性相似性对原始链接关系网络进行增强,从而降低网络稀疏性和噪声对节点划分的影响。实验对比表明该方法不仅能够处理不同节点属性类型的网络,而且具有较高的划分准确率。2)提出了主动融合先验信息的社区发现方法。对于社区结构不清晰的网络,通常难以准确选取聚类个数和初始中心,而且节点容易划分错误。基于主动学习,提出一种主动选择节点和链接的策略。该方法是一种双向方法,通过增强节点到所属类的凝聚力并增大类间距离使边界清晰化,从而提高节点划分的准确率。而且,通过主动选择节点,能够自动估计社区个数并选择初始中心。该方法能够以少量的人工标注,显著提高节点划分的准确率。3)提出了一种自适应融合链接结构信息和节点内容属性信息的社区发现方法(Adapt fusion of structural and attribute information, Adapt-SA)。该方法是一种局部加权的K-means模型,通过交替迭代,能够自动学习每个节点在两种异构信息的融合权重以及节点划分的隶属度矩阵。该方法得到的节点划分结果,使得同类的节点不仅链接紧密,而且具有较高的属性相似性。理论和实验验证了算法的收敛性,实验分析了模型对信息融合权重学习的有效性。通过与其他融合节点属性的社区发现方法对比,表明了Adapt-SA方法的性能。4)提出了不确定属性网络中的社区发现方法。现实网络中节点之间的边通常具有不确定性,而且节点具有高维的属性信息。针对这类复杂的网络数据,本章提出不确定属性网络的社区发现方法,综合考虑边的不确定性以及节点的属性信息。通过边的不确定性提取出重要的节点属性,进一步利用重要属性减弱边的不确定性以挖掘有意义的社区结构。人工网络以及实际网络的实验对比证明了方法的有效性,参数的实验分析验证了对抽样数以及权重阈值的鲁棒性。
【图文】：

主要工作,社区,中心度,节点

合节点链接关系和节点属性的社区发现方法（见第五章）。考虑网络中链接关系逡逑的不确定性，对不确定网络中融合节点属性信息的社区发现方法进行初步探索逡逑（见第五章）。图１．２给出本论文四个研宄内容的关系框架图，其详细介绍如下：逡逑１）基于节点中心度和离散度的社区发现方法逡逑Ｋ－ｍｅａｎｓ型网络社区发现方法中，聚类个数和初始中心选择是研宄的重点和逡逑难点，以往方法大多需要引入额外参数。针对这个问题，本文根据网络数据的特逡逑性，基于网络中节点的中心度和离散度，从决策图和综合得分两个角度给出确逡逑定聚类个数的方案，为Ｋ－ｍｅａｎｓ型方法提供一种新的初始中心节点的选择策略，逡逑并提出一种无参数调节的社区发现方法Ｋ－ｒａｎｋ－Ｄ。基于此，进一步对融合节点属逡逑性网络的社团划分方法进行研宄，提出基于节点的属性增强的方法ＡＮＮ－ｅｎｈａｎｃｅ。逡逑该方法利用节点的属性相似性对原始链接关系进行增强，从而降低网络稀疏性和逡逑噪声对节点划分的影响。逡逑１２逡逑

特殊网络,派系

殊网络（记为特殊网络１）由三个类组成，其中一个类是由４００个节点构成的很大逡逑的派系（全连接的团），其他两个类都是１３个节点构成，这三个类彼此通过一条逡逑边相连，如图２．１邋（ａ）所示。第二个特殊网络（记为特殊网络２）由１００个小派系，逡逑每一个派系有５个节点，这些派系彼此通过一条边首尾相接，从而形成一个类似逡逑环形的结构，图２．１邋（ｂ）展示了一个由５个派系组成的例子。逡逑（二）真实数据集逡逑真实数据集可细分为只有链接结构的数据及融合链接结构和节点属性的数逡逑据。逡逑（１）链接结构网络逡逑？逦Ｚａｃｈａｒｙ’邋ｓ邋ｃｌｕｂ网络又称Ｋａｒａｔｅ网络｜１３１】，是空手道俱乐部网络，，由３４个节逡逑点组成，每个节点表示一个成员，边表示成员之间的社交关系。由于俱乐部逡逑主管和校长发生矛盾，俱乐部成员就分成了分别以主管和校长为中心的两个逡逑类。逡逑？逦Ｒｉｓｋ网络［１３２］是一个具有４２个节点６个类的网络，该网络表示一个很流行的逡逑棋盘游戏；逡逑？逦Ｄｏｌｐｈｉｎｓ网络【１３３］是由６２个海豚构成，连边表示两个海豚之间接触频繁，被逡逑分成２个群体。逡逑？逦Ｌｅｓｍｉｓ网络［１３４］是根据Ｖｉｃｔｏｒ邋Ｈｕｇｏ的小说《悲惨世界》中角色是否同时出现逡逑而建立的
【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP311.13

【参考文献】