大数据 云计算
数码世界 P .141
袁璐 郑策 山东工程职业技术大学
摘要：在现代化社会发展的背景下，科技的发展取得了不小的进步，而本文主要对大数据时代下的图聚类算法以及其在社会关系网络
中的应用进行进一步的分析和研究，以此为相关工作提供参考。
关键词：图聚类 社会关系网络 应用
在大数据时代下，聚类这种不用监督的学习算法占有非常重要的地位。随着科技的不断发展，聚类算法的研究也取得了非常大的进步。而本文主要对图聚类的算法进行分析和研究，并在划分的图聚类中，对点和点之间距离的计算方法重点进行比较同时也比较其对聚类结果的硬性。还有因社会关系网络图中的点是没有坐标值的，因此无法使用曼哈坦距离和欧几里得距离，但可以使用K-medoids 聚类算法。在使用此聚类算法时，可以使用随机漫步距离算法和最短距离算法，社会关系网络图通过DBLP 数据集构成各个子图，并结合相关实验数据对两种算法的优缺点进行验证，从而进一步得到最短距离算法获得的聚类效果最佳。 一、聚类、图聚类以及社会网络综述
聚类指的是把数据集分成若干类或簇的过程，从而使不同类数
自动化控制系统据对象的相似度较低的让同时使同类数据对象的相似度较高。而目前的聚类算法有：层次聚类算法、网格聚类算法、划分聚类算法、密度聚类算法以及模型聚类算法等。
在对聚类进行分析时，其变体是一项非常有挑战的研究课题，即图聚类。而其主要指的是把图中相关的边分以及相对连接紧密的结点组成一个可以用一个抽象结点来表示的子图。其子图内各结点的相似性比较高，但子图之间的结点只有较低的相似性。另外图聚类有许多不同的方式，突出的有基于密度的聚类、Markov 聚类以及谱聚类等。
社会网络分析在20世纪30年代被提出，并成为一种相对比较重要的社会定量研究方法。其主要指社会成员以及社会成员之间关系的集合，并用来表示成员间各种社会关系的边以及各成员的节点，从而组成图结构，进而对社会网络进行描述[2]。另外，社会关系有很多种表现形式，例如：上下级之间的关系、文章合著关系、朋友之间的关系以及科研合作关系等。还有社会网络关系的图聚类算法主要有：Kernighan-lin 算法、G-N 算法、Newman 算法、过滤算法以及谱平分算法等。
zmma二、图聚类的算法
1、最短路径距离算法
橡皮弹在图论研究中比较经典的一个算法问题就是最短路径问题，而最短路径问题时在图中的两个点之间一个最短的路。最短路径距离算法也叫作Dijkstra 算法，其思想是：设G=（V ,E,W）的带权有向图。也就是说先把图中的顶点几何V 组成两组，一组是对最短路径的顶点集合（S）已求出，另一组是对其余最短路径的顶点集合（U）未求出，然后把未求出最短路径的顶点根据最短路径长度的增长顺序依次加入到已求出最短路径的顶点集合中去。
2、随机漫步距离算法
若P 是一个由多个（N）顶点组成的图GN×N 转移概率矩阵，那么此矩阵的第i 行第j 列的元素为第i 个顶点一步跳转到第j
个顶点的概率值；若是随机漫步从第i 个顶点到第j 个顶点走的最大步长，并假设随机漫步起始概率为c ∈（0,1），那么随机漫步的第i 个顶点到第j 个顶点距离的定义为：
其中T 指的是第i 个顶点到第j 个顶点的一
条路径，步长使lengh（T），对应的转移概率是P（T）。而随机漫步距离矩阵指的是各顶点之间的随机漫步距离组成的矩阵，其公示为：
王羽西
，其中，P 是图G 的转移概率，R i 是l 步内可
达到的随机漫步距离矩阵。
3、K-medoids 算法
K-medoids 算法的工作过程为：先随机从n 个数据对象中挑选k 个对象当作初始聚类的中心，而剩下的其他对象就按照他们和这些聚类中心的距离依次分配到和其最相似的聚类；其次，对各个聚类的新聚类中心进行再次计算时，可选择此聚类中距离均值点最近的真实点，并不断对这个过程进行重复，从而使各个点的分配不在出现变化的同时也能得到满足。在这个算法中，初始聚以K 个对象为中心点，之后以局部最佳结束，但这个方法对孤立点非常敏感。因此，在对这个算法进行改进时，初始聚类的中心点先随机选取一个来当做对象；
其次，对第二个聚类中心点进行选取时，其和初始聚类的中心点的距国营农场
离要最远；然后到选取去第三个聚类中心点时，和第二个聚类中心点的挑取一样，并依次类推，直到第k 个聚类中心点为止。
三、实验
1、衡量指标
衡量指标用density 来表示，若图是无向图，那么就先要对整个大图进行统计，而图在没有进行分割之前，总共有n 条边，然后依次计算k 类的每类包含的点之间的边数，假如分别是
n 1,n 2,...,n k ，那么最后的计算就是density=（n 1+n 2+...+n k ）/n。
当用程序将这个算法进行实现后，其运行程序收集数据，指在每个K 值的情况下，需要进行10次分类，之后取10次分类比率的比均值当做前k 值下的最后比率density ，通过两个算法的density 值比较出优劣，其中，最短距离算法得到的比率用density1
项目管理职业资格认证表示，随机漫步距离算法得到的比率用density2表示，对比如图1所示。
图1随机漫步距离和最短距离的比率图
从图中可以看出，随着分的类逐渐增多，类和类之间的边也就增多，
相反类内部的边就越少，因此density 呈现下降趋势；还有最短距离算法和随机漫步距离算法相比，最短距离算法获得的density 较高。
2、聚类效果
使用最短距离算法，把大小数据划分成15小类，每类数据是相同领域合著关系比较紧密的作者编号，通过实验证明，分类成效非常理想。结合每个作者之间合著文章的论文数量，画出分类之前的分布图（如图2），经过重复迭代，最后分成15小类，而这时的分布图如图3.最后实验情况和实际情况相同，分类结果比较理想。
图2 分类前的点分布图 图3 分类后的点分布图
四、结束语
在图聚类进行研究时，使用随机漫步算法和最短距离算法这两种不同的距离算法来衡量各个点之间的相异度。而DBLP 数据集建立的合作关系社会网络图，使用K-medoids 聚类算法，把大图分为K 类，使相同领域合著关系比较紧密的划分在同一类当中，最后通过实验数据得出，最短距离算法获得的聚类效果比较理想。
参考文献
[1]姜斐.基于聚类算法的网络行为计算研究[D].南京邮电大学,2016.[2]金超.基于图聚类的社会网络数据挖掘算法研究[D].山东理工大学,2016.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议