论文总字数：23807字

摘 要

网络社团研究是近年来图数据挖掘领域的研究热点。社团是指网络中存在的模块化结构，社团之间的连接相对稀疏，而社团内部的连接相对紧密。社团发现和搜索是网络社团研究的基础问题。社团发现是指利用网络拓扑结构所隐藏的信息从大型网络中分析出具有模块化特征的社团结构的过程。社团搜索是指给定一个节点集，从大型网络中找出包含这个节点集的社团的过程。

然而，几乎所有的社团发现和搜索算法都没有考虑到社团的影响力问题，而在许多现实应用中我们需要用到影响力社团，例如，数据库研究领域的研究人员希望能找到数据库领域中最具影响力的研究者团队来了解该领域的研究趋势，社交网站的新用户希望找到自己感兴趣话题的影响力团队来获得更多资讯。因此，本文基于k-核提出k-影响力社团模型用于发现影响力社团。进一步，在k-影响力社团模型的基础上，本文提出了基于k-核的直接发现算法和基于DFS的发现算法。在计算机领域合著者关系网络和文章引用网络数据集上大量实验，改变k值和r值，利用不同的节点权重向量，从而验证所提算法的效益和效率。

影响力社团的发现是一个新的研究方向，值得深入研究。在本文的最后，我们提出了一些影响力社团发现的新思路，进一步提高算法性能，社团影响力值的确定，自定义节点权重的确定和应用于动态网络的算法开发等等。

关键词：网络社团；社团发现；社团搜索；k-核；k-影响力社团；DFS算法

Influential Community Detection in Networks

Abstract

Community detection in networks has attracted much attention in recent years. There are some community structures in many real-world networks, such as social networks and biological networks. Another related but different problem is community search. Its goal is to find the most likely community that contains the query nodes. The difference between these two problems is that the community detection problems is to identify all communities in a network by optimizing some pre-defined criterions, while the community search problem is a query-dependent variant of the community detection problem, which aims to find the community that contains the query node.

However, in almost all the previous studies on these problems, a community is defined as a densely connected subgraph which ignores the influence of a community. However, we are interested in finding the most influential communities in many application domains. In this paper, we introduce a new community model called k-influential community based on the concept of k-core, which can capture the influence of a community. Based on this new model, we propose the k-core based detection algorithm and the DFS-base detection algorithm. We do some experiments on 2 real-word networks to demonstrate the efficiency and effectiveness of the proposed algorithm.

Influential community detection in networks is a new research area. So, we can improve the algorithm in many ways. At the end of the paper, we propose some new ideas to implement more efficient algorithms.

KEY WORDS: community, community detection, community search, k-core, k-influential community, DFS

目 录

摘 要 1

Abstract 2

第一章 绪 论 4

1.1 引言 4

1.2 网络社团研究现状 4

1.3 社团研究的常用方法 5

1.3.1 社团发现算法 5

1.3.2 社团搜索算法 6

1.3.3 紧密结合子图挖掘算法 6

1.4 本文的研究目的和主要研究内容 6

1.5 论文组织结构 7

第二章 算法设计 8

2.1 相关定义 8

2.2 基于k-核的直接发现算法 11

2.3 基于DFS的发现算法 12

2.4 本章小结 13

第三章 实验及结果分析 14

3.1 实验环境及数据集 14

3.2 实验设计 14

3.3 合著者关系网络分析 14

3.3.1 k和r值变化对结果的影响 14

3.3.2 两种算法性能比较 17

3.4 文章引用关系网络分析 18

3.5 本章小结 24

第四章 总结与展望 25

4.1 总结 25

4.2 展望 25

致谢 27

参考文献 28

第一章 绪 论

• 1. 引言

随着信息化的快速发展，当今世界进入了数据大爆炸的时代。数据越来越多，如何从这些数据中提取出自己所需的信息并在各个领域中得到应用，即数据挖掘，引起了广泛的关注。数据挖掘是计算机研究领域的一个热门研究方向。它涉及到统计、在线分析，机器学习，信息检索和模式识别等多个方面。

数据挖掘是经历数据准备、挖掘、评估、参数调整、再挖掘等等过程。数据挖掘中对挖掘结果解释是一个重要操作部分。数据挖掘涉及到的数据有各种类型，例如文本、图片、视频，这一方面的数据挖掘就是提取其特征；而对于图、树结构的数据，数据挖掘注重于发现数据间的关联关系和数据的内容。数据挖掘之前应该充分了解数据集的特点，观察数据集的是否稀疏、如何分布及数据的覆盖范围等等。数据挖掘首先需要定义怎么样的数据才是相似的，评价数据的相似性是数据挖掘的基础工作。在数据挖掘之前对数据进行预处理可以提高效率以得到更优的结果。在数据挖掘之后要对结果进行评析，可视化是一种有效方法，可以直观的看到结果的正确性。

剩余内容已隐藏，请支付后下载全文，论文总字数：23807字