分布式K-Core算法加速求解最大团问题及在金融社交网络中应用
发布时间：2020-11-15 11:51
随着互联网技术的不断提高和普及,越来越多的用户加入社交网络平台,从而形成了大规模的社交网络,分析和挖掘社交网络隐藏的信息是非常具有研究价值的。最大团是社交网络中联系最紧密的结构,因此通过最大团来分析社交网络是非常有效的方式。最大团问题(Maximal Clique Problem,MCP)是一类经典的NP-完全问题,在现实生活领域获得广泛的应用。本文通过研究K-Core算法,发现K-Core算法通过不断迭代剪枝能够获取到一个最大近似团,并且在最大近似团中可能包含有最大团。因此,本文提出先使用K-Core算法对图进行剪枝获得最大近似团,然后使用分支限界法获得最大团的研究方法。并且,为了处理具有海量数据的社交网络的场景,本文通过使用Spark分布式内存框架,实现了分布式K-Core算法。本论文的主要的工作内容如下:1,通过将K-Core算法和分支限界算法结合,通过实验证明了算法具有提升分支限界算法搜索最大团的效率。2,将K-Core算法和Spark分布式计算框架结合,设计和实现了分布式K-Core算法,并通过实验证明了算法的可行性。3,将算法应用到真实的大型金融社交网络——BoardEx中。在BoardEx中通过组合算法挖掘出最大团,分析其中的职位信息,发现在这个缩小图中的职位比例近似于原始社交网络的职位比例,说明在获取的最大团能够在一定程度上代表BoardEx社交网络进行某些特征的数据分析。
【学位单位】：暨南大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5;TP301.6
【部分图文】：
2.1 社交网络的属性现阶段的社交网络具有海量的用户和错综复杂的关系，和社交网络在结构上都存在着相同的属性，而这些属性在大型社交网络中表现更加明显。其中最具有代表性的三个属性：无尺度分布（scale-free distribution）[24]、小世界效应（thesmall-world effect）[24]和强的社区结构（strong community structure）[24]。2.1.1 无尺度分布无尺度分布（scale-free distribution）在图论中也被称为幂率分布（power lawdistribution）[25]，如图 2-1 所描述的是拥有 1138499 个顶点 YouTube 和拥有17115255 条边 Wiki[26]这两个社交网络中顶点的度分布情况，从图中可以看出，这两个社交网络中大多数的顶点的度都是比较低的，而只有少数顶点拥有较高的度，如度值大于 103。并且在图中顶点的度分布可以用近似线性模式表达出来，所以就将符合这种模式特征的分布称为幂率分布，即无尺度分布。
分布式 K-Core 算法加速求解最大团问题及在金融社交网络中应用.2.1 最大团问题的定义团在图论中的定义是：在图 G（V，E），其中 V 表示图 G 中的顶点，E 表 G 中的边，存在着任意两个顶点都有边相互连接的子图结构，就将该子图称为团。如果存在着这样的团，并且该团不是其他团的真子集，符合这种条团被称为极大团（maximal clique）[36]。若在极大团中，某个极大团的顶点最多，则将这个极大团称为最大团（maximum clique）[36]。团的大小指的是所包含的顶点个数，即如果团中包含的顶点个数为 k，则称为 k 团，如图示，描述的是 3 团，4 团和 5 团三个团结构。
图 2-3 最大团的问题描述观察如图 2-3，可知无向图 G（V，E）是由 10 个顶和 24 条边构成的，通过枚举出这个无向图 G 中的团结构，可以分解出 6 个团结构，很显然这六个团结构都满足属性2和属性4，而在这6个团中，顶点数目最多的是最后一个团Clique它包含有 5 个顶点，并且 Clique6 满足团的四个属性，所以 Clique6 被认为是图G 中的最大团。最大团问题就是通过最大团搜索算法在图 G 中找出和 Clique6 一样的结构的子图问题。最大团问题如果通过数学模型进行描述的话，可以通过整型规划的方式进行描述，具体推导过程如下：设 , t(x)={i ∈ } , ∈ , ∈ , 则t 其中∈, n 为图的顶点数。tt（2.1）
【参考文献】
本文编号：2884724
【学位单位】：暨南大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5;TP301.6
【部分图文】：
2.1 社交网络的属性现阶段的社交网络具有海量的用户和错综复杂的关系，和社交网络在结构上都存在着相同的属性，而这些属性在大型社交网络中表现更加明显。其中最具有代表性的三个属性：无尺度分布（scale-free distribution）[24]、小世界效应（thesmall-world effect）[24]和强的社区结构（strong community structure）[24]。2.1.1 无尺度分布无尺度分布（scale-free distribution）在图论中也被称为幂率分布（power lawdistribution）[25]，如图 2-1 所描述的是拥有 1138499 个顶点 YouTube 和拥有17115255 条边 Wiki[26]这两个社交网络中顶点的度分布情况，从图中可以看出，这两个社交网络中大多数的顶点的度都是比较低的，而只有少数顶点拥有较高的度，如度值大于 103。并且在图中顶点的度分布可以用近似线性模式表达出来，所以就将符合这种模式特征的分布称为幂率分布，即无尺度分布。
分布式 K-Core 算法加速求解最大团问题及在金融社交网络中应用.2.1 最大团问题的定义团在图论中的定义是：在图 G（V，E），其中 V 表示图 G 中的顶点，E 表 G 中的边，存在着任意两个顶点都有边相互连接的子图结构，就将该子图称为团。如果存在着这样的团，并且该团不是其他团的真子集，符合这种条团被称为极大团（maximal clique）[36]。若在极大团中，某个极大团的顶点最多，则将这个极大团称为最大团（maximum clique）[36]。团的大小指的是所包含的顶点个数，即如果团中包含的顶点个数为 k，则称为 k 团，如图示，描述的是 3 团，4 团和 5 团三个团结构。
图 2-3 最大团的问题描述观察如图 2-3，可知无向图 G（V，E）是由 10 个顶和 24 条边构成的，通过枚举出这个无向图 G 中的团结构，可以分解出 6 个团结构，很显然这六个团结构都满足属性2和属性4，而在这6个团中，顶点数目最多的是最后一个团Clique它包含有 5 个顶点，并且 Clique6 满足团的四个属性，所以 Clique6 被认为是图G 中的最大团。最大团问题就是通过最大团搜索算法在图 G 中找出和 Clique6 一样的结构的子图问题。最大团问题如果通过数学模型进行描述的话，可以通过整型规划的方式进行描述，具体推导过程如下：设 , t(x)={i ∈ } , ∈ , ∈ , 则t 其中∈, n 为图的顶点数。tt（2.1）
【参考文献】
相关期刊论文 前4条
1 谢平;邹传伟;;互联网金融模式研究[J];金融研究;2012年12期
2 王青松;范铁生;;低度图的最大团求解算法[J];计算机工程;2010年06期
3 王丽爱;周旭东;陈崚;;最大团问题研究进展及算法测试标准[J];计算机应用研究;2007年07期
4 郭长庚;潘晓伟;;对最大团问题的HEWN算法分析[J];河南科学;2006年05期
本文编号：2884724
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/2884724.html
