论文部分内容阅读
近年来,以在线社交网络和电子商务为代表的社会媒体网络迅猛发展。社区发现能够揭示网络的组织结构,有助于理解复杂网络的功能、发现网络中蕴含的规律,作为一种重要的社会网络分析技术,引起了学者的广泛关注。本文围绕社会网络中的社区发现和搜索方法开展研究。具体地,本文的主要研究工作围绕以下几方面:
目前大多数全局社区发现算法主要依赖网络节点间的连接关系识别社区结构,忽视了网络节点影响力的差异。针对该问题,提出一种基于中心极大团扩展的社区发现算法。该算法首先选择分散在网络中的几个内聚且有影响力的中心极大团作为初始社区,然后采用局部模块度扩展的方法将初始社区外的节点划分到与其连接最紧密的社区中。实验结果表明该算法能够更好地揭示网络中的社区结构。
局部社区发现作为一种只利用给定节点周围的网络结构就可以找出该节点所在社区的方法,在大规模社会网络分析中具有重要的研究意义。针对已有局部社区发现算法需要人工设置参数、准确率低的问题,提出基于加权共同邻居相似度的局部社区发现算法。为了更好地度量节点间的相似度,提出加权邻居节点的共同邻居相似度指标;然后给出一种新的局部社区质量度量指标,在保持社区度量指标值不下降的前提下,通过加入与当前局部社区嵌入度最大的节点的方法找出给定节点所在社区。实验结果表明该算法能有效地挖掘出给定节点所在的局部社区。
社区搜索是一种面向查询的社区发现问题,不同于局部社区发现算法只能利用给定节点周围的网络结构,社区搜索算法不仅可以利用给定节点周围的网络结构而且也可以利用网络的整体结构。基于深度学习的节点嵌入技术能够自动从网络结构中学习节点的低维实值向量表示,为解决社区搜索问题提供了新的方法。针对不带返回节点个数限制的社区搜索问题,提出基于共同邻居随机游走节点嵌入的社区搜索算法。首先构建基于共同邻居随机游走的节点嵌入模型,通过该模型学习节点的低维向量表示;然后通过从外壳节点集合中选择与当前社区相似度最高的节点的方法不断扩展当前社区,从而实现一种新的社区搜索算法。实验结果验证了该算法的有效性和高效性。
针对带返回节点个数限制的社区搜索问题,提出一种基于节点嵌入表示学习的社区搜索算法。首先针对已有节点嵌入算法存在着较高的概率在最亲近邻居间来回游走的问题,提出基于最亲近邻居但不立即回访随机游走的节点嵌入模型,通过该模型将网络中的节点映射到低维向量空间中的点。借鉴多维空间中几何中心的思想,采用社区内所有节点的向量均值作为社区的向量表示,通过选择与当前社区距离最近的节点加入社区的方法,实现一种新的社区搜索算法。实验结果表明该社区搜索算法具有更高的准确性。
综上所述,本文主要围绕社会网络中的社区发现和搜索相关问题开展研究,对全局社区发现、局部社区发现、不带返回节点个数限制的社区搜索以及带返回节点个数限制的社区搜索四个问题进行了分析和解决。希望本文的研究成果能够对社会网络中的社区发现和搜索相关研究有所裨益。
目前大多数全局社区发现算法主要依赖网络节点间的连接关系识别社区结构,忽视了网络节点影响力的差异。针对该问题,提出一种基于中心极大团扩展的社区发现算法。该算法首先选择分散在网络中的几个内聚且有影响力的中心极大团作为初始社区,然后采用局部模块度扩展的方法将初始社区外的节点划分到与其连接最紧密的社区中。实验结果表明该算法能够更好地揭示网络中的社区结构。
局部社区发现作为一种只利用给定节点周围的网络结构就可以找出该节点所在社区的方法,在大规模社会网络分析中具有重要的研究意义。针对已有局部社区发现算法需要人工设置参数、准确率低的问题,提出基于加权共同邻居相似度的局部社区发现算法。为了更好地度量节点间的相似度,提出加权邻居节点的共同邻居相似度指标;然后给出一种新的局部社区质量度量指标,在保持社区度量指标值不下降的前提下,通过加入与当前局部社区嵌入度最大的节点的方法找出给定节点所在社区。实验结果表明该算法能有效地挖掘出给定节点所在的局部社区。
社区搜索是一种面向查询的社区发现问题,不同于局部社区发现算法只能利用给定节点周围的网络结构,社区搜索算法不仅可以利用给定节点周围的网络结构而且也可以利用网络的整体结构。基于深度学习的节点嵌入技术能够自动从网络结构中学习节点的低维实值向量表示,为解决社区搜索问题提供了新的方法。针对不带返回节点个数限制的社区搜索问题,提出基于共同邻居随机游走节点嵌入的社区搜索算法。首先构建基于共同邻居随机游走的节点嵌入模型,通过该模型学习节点的低维向量表示;然后通过从外壳节点集合中选择与当前社区相似度最高的节点的方法不断扩展当前社区,从而实现一种新的社区搜索算法。实验结果验证了该算法的有效性和高效性。
针对带返回节点个数限制的社区搜索问题,提出一种基于节点嵌入表示学习的社区搜索算法。首先针对已有节点嵌入算法存在着较高的概率在最亲近邻居间来回游走的问题,提出基于最亲近邻居但不立即回访随机游走的节点嵌入模型,通过该模型将网络中的节点映射到低维向量空间中的点。借鉴多维空间中几何中心的思想,采用社区内所有节点的向量均值作为社区的向量表示,通过选择与当前社区距离最近的节点加入社区的方法,实现一种新的社区搜索算法。实验结果表明该社区搜索算法具有更高的准确性。
综上所述,本文主要围绕社会网络中的社区发现和搜索相关问题开展研究,对全局社区发现、局部社区发现、不带返回节点个数限制的社区搜索以及带返回节点个数限制的社区搜索四个问题进行了分析和解决。希望本文的研究成果能够对社会网络中的社区发现和搜索相关研究有所裨益。