基于网络表示学习的社区发现技术研究
发布时间：2021-08-17 16:39
随着在线社交网络的日趋复杂,网络节点逐渐成为负载多源信息的富节点,除了网络的拓扑结构信息,节点本身的其他信息也是重要的数据源,譬如,社交网络中用户的属性资料和生成文本。现有的社区发现算法多数是针对网络拓扑结构实现社区划分的,并没有充分利用用户特征,检测得到的社区结构不能准确反映社交网络的组织机理,对现实世界社区发现问题的研究提出不小的挑战。针对上述问题,本文从如何融合多源信息来准确刻画用户特征及如何基于用户的特征表示实现社区划分两个问题展开研究,主要的研究工作包括以下两个方面:第一,为了更准确地刻画复杂多源网络的用户特征,研究了一种基于网络表示学习的用户表示模型User2vec。首先,建立三个独立的特征表示向量。其中,从用户的属性信息提取特征并建立属性表示向量info2vec;从用户生成文本分离出多粒度的文本内容,采用TF-IDF、LDA、Doc2vec多种算法从不同文本内容提取特征并生成文本表示向量blog2vec;从用户的文本内容扩展稀疏的网络结构,并将网络表示学习技术应用到扩展网络结构中,建立增强网络表示向量graph2vec。然后,提出两种融合多源信息的用户表示模型User2v...
【文章来源】：国防科技大学湖南省 211工程院校 985工程院校
【文章页数】：81 页
【学位级别】：硕士
【部分图文】：
社区发现算法总览图
绫尘跋律缜?⑾至煊虼嬖诘奈侍庖约懊媪俚奶粽健Ｍ?1.1 社区发现算法总览图1.2.1 非重叠社区发现算法社区发现，从本质上讲，等同于图分割问题，即将网络的图结构分割成若干个子图，其划分依据是网络的拓扑结构。那么，传统的图划分和图聚类算法能够有效地解决简单的社区发现问题。图划分算法关注如何识别网络的强弱连边关系。Kernighan-Lin 算法[2]采用贪婪的优化策略实现图划分，其主要思想是先为网络定义一个增益函数，通过贪婪搜索的方式寻找最优的社区划分结果，而且此时的增益函数值达到最大。该算法给出最优的网络划分，且通过树状图实现层次社区结构的可视化，但是该算法的缺点在于需要首先指定两个子社区的规模。另外，谱二分法是另一种应用于社区发现问题的经典算法。如果计算得到的拉普拉斯矩阵的第二特征值越小，则划分得到的社区效果越好。于是，谱二分法划分社区的关键在于 Laplacian 矩阵特征值中第二小值的计算，算法的缺点是多个社区结构的划分效率比较低。
图 1.3 派系过滤算法主要思想示意图将标签传播思想应用到重叠社区发现问题。其中，Steve Gregory 改进 LPA 算法，提出 COPRA 算法[22]。算法引入标签二元组(c,b)，通过计算邻接点标签的隶属度来度量其传播能力，同时该算法改变 LPA 算法原先的终止条件，通过跟踪每轮计算结束后剩余标签集合的大小来判断算法是否结束，即当集合的大小不再变化更新，则算法结束，对应的社区划分即为最终的社区结构。社区结构是一种局部结构，某个社区的形成只取决于网络局部的连接关系，其他区域的拓扑结构对其无任何影响。于是，Andrea Lancichinetti 等人于 2009 年根据局部扩展优化的思想，提出了 LFM 算法[23]，以若干个节点为种子社区，不断扩大节点社区的覆盖范围，从而迭代生成所有节点的归属社区，得到原始网络结构的最终社区划分，但是算法发现的社区结构重叠程度较低。除此之外，2010 年，ConradLee 等人提出了另一种局部扩展优化算法 GCE[24]，可以发现重叠度更高的社区结构。Huang 等人于 2011 年提出了一种无参的层次网络聚类算法 DenShrink[25]，将基于密度的层次聚类算法与模块度优化算法相结合，解决大规模加权有向网络的层次社区结构检测问题。
【参考文献】：
期刊论文
[1]网络表示学习综述[J]. 涂存超,杨成,刘知远,孙茂松. 中国科学:信息科学. 2017(08)
[2]网络表示学习[J]. 陈维政,张岩,李晓明. 大数据. 2015(03)
[3]一种基于主题相似性和网络拓扑的微博社区发现方法[J]. 王卫平,范田. 计算机系统应用. 2013(06)
[4]复杂网络社团发现算法研究新进展[J]. 骆志刚,丁凡,蒋晓舟,石金龙. 国防科技大学学报. 2011(01)
本文编号：3348118
【文章来源】：国防科技大学湖南省 211工程院校 985工程院校
【文章页数】：81 页
【学位级别】：硕士
【部分图文】：
社区发现算法总览图
绫尘跋律缜?⑾至煊虼嬖诘奈侍庖约懊媪俚奶粽健Ｍ?1.1 社区发现算法总览图1.2.1 非重叠社区发现算法社区发现，从本质上讲，等同于图分割问题，即将网络的图结构分割成若干个子图，其划分依据是网络的拓扑结构。那么，传统的图划分和图聚类算法能够有效地解决简单的社区发现问题。图划分算法关注如何识别网络的强弱连边关系。Kernighan-Lin 算法[2]采用贪婪的优化策略实现图划分，其主要思想是先为网络定义一个增益函数，通过贪婪搜索的方式寻找最优的社区划分结果，而且此时的增益函数值达到最大。该算法给出最优的网络划分，且通过树状图实现层次社区结构的可视化，但是该算法的缺点在于需要首先指定两个子社区的规模。另外，谱二分法是另一种应用于社区发现问题的经典算法。如果计算得到的拉普拉斯矩阵的第二特征值越小，则划分得到的社区效果越好。于是，谱二分法划分社区的关键在于 Laplacian 矩阵特征值中第二小值的计算，算法的缺点是多个社区结构的划分效率比较低。
图 1.3 派系过滤算法主要思想示意图将标签传播思想应用到重叠社区发现问题。其中，Steve Gregory 改进 LPA 算法，提出 COPRA 算法[22]。算法引入标签二元组(c,b)，通过计算邻接点标签的隶属度来度量其传播能力，同时该算法改变 LPA 算法原先的终止条件，通过跟踪每轮计算结束后剩余标签集合的大小来判断算法是否结束，即当集合的大小不再变化更新，则算法结束，对应的社区划分即为最终的社区结构。社区结构是一种局部结构，某个社区的形成只取决于网络局部的连接关系，其他区域的拓扑结构对其无任何影响。于是，Andrea Lancichinetti 等人于 2009 年根据局部扩展优化的思想，提出了 LFM 算法[23]，以若干个节点为种子社区，不断扩大节点社区的覆盖范围，从而迭代生成所有节点的归属社区，得到原始网络结构的最终社区划分，但是算法发现的社区结构重叠程度较低。除此之外，2010 年，ConradLee 等人提出了另一种局部扩展优化算法 GCE[24]，可以发现重叠度更高的社区结构。Huang 等人于 2011 年提出了一种无参的层次网络聚类算法 DenShrink[25]，将基于密度的层次聚类算法与模块度优化算法相结合，解决大规模加权有向网络的层次社区结构检测问题。
【参考文献】：
期刊论文
[1]网络表示学习综述[J]. 涂存超,杨成,刘知远,孙茂松. 中国科学:信息科学. 2017(08)
[2]网络表示学习[J]. 陈维政,张岩,李晓明. 大数据. 2015(03)
[3]一种基于主题相似性和网络拓扑的微博社区发现方法[J]. 王卫平,范田. 计算机系统应用. 2013(06)
[4]复杂网络社团发现算法研究新进展[J]. 骆志刚,丁凡,蒋晓舟,石金龙. 国防科技大学学报. 2011(01)
本文编号：3348118
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/3348118.html
