并行图计算方法在社交网络社区划分中的研究与实现

发布时间：2020-05-31 01:35

【摘要】：大规模复杂网络下使用并行图计算的意义在于,将并行计算、图、社区划分算法相融合使得社交网络社区划分更精准、更快速、更可靠等,该研究对社区群体行为分析、社区情感分析、推荐系统、广告定向投放及社会维稳等有广泛的实际应用意义。通过采用改进的谱聚类算法并实行并行化,在改进算法中主要使用三角模型的方式计算社交网络节点间的相似性,从而改变了谱聚类邻接矩阵构造过程。最后,使用社区划分评价指标模块度度改进算法的效率进行了度量,并将该算法与目前较好的社区划分算法做了对比,在对比中体现出本文算法在高效、准确、可扩展方面的优势。研究表明社区划分特点是社区内紧密性较高,社区间紧密型较低,在大规模网络图中,社区划分后依然存在社区重叠区域较多的问题,考虑到这些因素可能导致社区划分的准确度降低,引入基于子图划分的聚类算法来检测重叠社区,从而优化改进的谱聚类算法在社区划分中的准确度并结合并行计算方式,综合以上方式进一步确定了本文提出方法的高效性、准确性、可靠性特征。通过结合大规模数据集Twitter数据集和Stanford Large Network Dataset Collection测试数据集进行相关实验,实验结果表明,本文提出的方法具有可扩展性,能快速、准确的对大规模复杂网络进行社区划分。
【图文】：

网络结构图,社交,网络结构,相似性

图 3. 1 社交网络结构采样图值的规范化拉普拉斯是谱聚类算法思想下重要的一个环值，基于三角模型求节点对相似性邻接矩阵构造。节点对相似性通过中，通过相似距离来衡量的不可定点相似性不可控性。通过这样的计，避免了人为误差，整个节点相似的数据可靠性。虽然通过三角模矩阵的构建，但提出了完全基于网较强相似性，社区之间相似性低，

三角模型,并行化,实现过程

输出：网络节点数据集的 k 个子图；4 规范化 Laplace 矩阵， = 12 12；5 并行化改进的谱聚类a = λ ，获得前 k 个最大特征值的特征向量 k；6 将前 k 个最大特征值的特征向量为列向量构建矩阵 n k；7 令-i k = ￠表示 V 的第 i 个行向量；8 将原来 n*n 的矩阵，降维到 n*k 维矩阵；9 并行化 k-means 算法，对 n*k 矩阵进行聚类，得到 k 个类群分别为： k；10 根据聚类的 k 群体，可视化网络结构。3.3.3 基于 Spark 的并行化实现基于 Spark 下的三角模型计算节点对相似性权值，三角模型在单机计算下的时间复杂度为(￠n )，在并行化下时间复杂得到了很大的改进，，利用 Spark 基于内存迭代计算的优势[17]，将大规模数据集使用分而治之的思想进行处理，三角模型并行化如图 3.2 所示。
【学位授予单位】：重庆邮电大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6;O157.5

【参考文献】