基于社会网络的数据挖掘方法研究

VIP免费

3.0 牛悦 2024-11-19 5 4 3.72MB 65 页 15积分

侵权投诉

摘要

现实生活中存在着各式各样的社会网络，例如，人际关系网、万维网、博客、

论坛、MSN、Facebook 以及生态食物链网等。社会网络是由一群个体和个体之间

的各种关系组成的集合，其中这些关系包括朋友关系、亲戚关系、上下级关系、

师生关系以及网友关系等。对大型社会网络进行研究，从中挖掘出一些有价值的

信息或模式，具有广泛的应用价值。其一，社会网络提供了许多新的交际方式，

可以通过互联网进行交友、交流、分享信息、找工作等；其二，社会网络给各个

领域带来了许多机遇与挑战，利用社会网络分析技术可以进行市场营销，预防计

算机病毒的传播，预测恐怖袭击，粉碎犯罪集团以及进行疫苗接种等。

本文主要针对社区发现算法和关键节点挖掘算法展开研究与讨论，所有的工

作都是基于这两方面来进行。介绍了社会网络分析技术，例如，中心性分析和社

区分析等。介绍了数据挖掘常用的聚类算法，经典的社区发现算法以及关键节点

挖掘算法，分析它们的性能、优缺点和适用范围等。当今社会网络规模都很庞大，

如果直接基于整个网络进行关键节点挖掘，其效率非常低下，没有应用价值，因

此本文结合社会网络的特性，创新性地提出了一种新的解决方案——基于社区进

行关键节点挖掘，该方案首先对整个网络进行社区发现，然后基于社区进行关键

节点挖掘，再对所有社区的关键节点求并集，得到整个网络的关键节点。由于社

会网络规模庞大且具有明显的社区结构，因此可以进行社区挖掘并且可以求得一

个近似解。经实验验证，对于规模庞大且具有明显社区结构的社会网络，采用本

文提出的解决方案进行挖掘是可行的，虽然准确度略有下降（在可接受的范围内），

但运行效率却得到了显著地提高。

在对社区进行关键节点挖掘方面，本文提出了一种动态的关键节点挖掘算法

——贪婪挖掘算法。与静态挖掘算法相比，该算法在挖掘的每一步动态地确定关

键节点，而不是从按影响度降序排序的节点中静态地选择前 k个节点作为关键节

点。经实验验证，贪婪挖掘算法与静态挖掘算法都能快速收敛，并且运行效率都

差不多，但是贪婪挖掘算法挖掘的总影响度要明显高于静态挖掘算法。因此，在

本文解决方案的关键节点挖掘部分，采用贪婪挖掘算法进行挖掘。

关键词：社会网络社区发现关键节点数据挖掘

ABSTRACT

In daily life, there are a great variety of social networks, such as, interpersonal

relationship, the World Wide Web, forums, MSN, Facebook, and ecological food webs

and so on. Social networks are a collection of relationships between individuals, which

include friendship, kinship, superior-subordinate relationship, teacher-student

relationship, etc. Mining on large-scale social networks for valuable information and

patterns has a wide field of application with good prospects. Firstly, social networks

provide many new ways of communication, such as making friends, exchanging and

sharing information, finding jobs and so on; Secondly, social networks bring many

opportunities and challenges in many areas. Social network analysis techniques are used

for marketing, preventing the spread of computer viruses, anti-terrorism, crime fighting,

vaccine inoculation and so on.

In this paper, we focus on community detection algorithm and key-nodes mining

algorithm. We first introduce social network analysis techniques, such as, central

analysis and community analysis. Then common clustering algorithm, the classical

community detection algorithm and key-nodes mining algorithms are presented with

their performance, advangtage and disadvantage and the scope of application. Because

of large-scale social networks, if we are directly mining key-nodes based on the whole

networks, the efficiency is very low, and the value is not applied. So According to the

characteristics of social networks, we propose a new solution, “Mining Key-Nodes

Based on Communities”. Firstly, discovering communities based on the whole networks.

Then mining key-nodes based on communities, and finally finding the union of all the

key-nodes. The experiments show that using the paper’s solution for mining large-scale

networks with obvious community structure is feasible. Although the solution reduced a

little accuracy, the efficiency of the solution has been improved significantly.

Finally, a greedy key-nodes mining algorithm, which is a dynamic mining

algorithm, proposed in the paper. Compared with the static key-nodes mining algorithm,

the greedy algorithm select the key-nodes dynamically in each step, rather than

selecting the key-nodes statically. The experiments show that two algorithms , which are

relatively stable, converge fast and have similar running time. But the greedy algorithm

has a significantly higher accuracy than the static algorithm.

Key Words：Social Networks，Community Detection，Key-Nodes，

Data Mining

摘要

ABSTRACT

第一章绪论...............................................................................................................1

§1.1 研究背景.................................................................................................1

§1.2 研究的目的及意义.................................................................................2

§1.3 研究现状.................................................................................................3

§1.4 论文研究内容及章节安排.....................................................................4

第二章社会网络分析.................................................................................................5

§2.1 社会网络.................................................................................................5

§2.1.1 社会网络的概念.........................................................................5

§2.1.2 社会网络的度量标准.................................................................6

§2.1.3 社会网络的研究内容.................................................................7

§2.2 中心性分析.............................................................................................8

§2.2.1 程度中心性.................................................................................8

§2.2.2 亲近中心性.................................................................................9

§2.2.3 中介中心性.................................................................................9

§2.3 社区分析...............................................................................................10

§2.4 本章小结...............................................................................................12

第三章基于社会网络的数据挖掘方法...................................................................13

§3.1 数据挖掘聚类算法...............................................................................13

§3.2 社区发现算法.......................................................................................15

§3.2.1 Kernighan-Liu 算法 ...................................................................15

§3.2.2 G-N 算法 ................................................................................... 16

§3.2.3 Radicchi 算法 ............................................................................ 18

§3.3 关键节点挖掘算法...............................................................................19

§3.3.1 PageRank 算法 .......................................................................... 20

§3.3.2 HITS 算法..................................................................................22

§3.4 本章小结.............................................................................................24

第四章基于社区的关键节点挖掘方法...................................................................25

§4.1 社会网络的特性...................................................................................25

§4.1.1 规模庞大...................................................................................25

§4.1.2 社区稳定性...............................................................................26

§4.1.3 中心性.......................................................................................27

§4.1.4 帕累托法则...............................................................................28

§4.2 挖掘算法的基本思想...........................................................................28

§4.2.1 问题描述...................................................................................28

§4.2.2 信息传播模型...........................................................................29

§4.2.3 算法基本思想...........................................................................30

§4.3 改进的社区发现算法...........................................................................31

§4.4 关键节点挖掘算法...............................................................................34

§4.4.1 随机挖掘算法...........................................................................34

§4.4.2 基于节点频度中心度的静态挖掘算法...................................35

§4.4.3 基于节点频度中心度的贪婪挖掘算法...................................36

§4.5 本章小结.............................................................................................39

第五章算法实现与实验分析...................................................................................40

§5.1 实验环境与数据集...............................................................................40

§5.2 数据预处理...........................................................................................41

§5.3 关键节点挖掘算法的实现...................................................................42

§5.3.1 随机挖掘算法的实现...............................................................42

§5.3.2 静态挖掘算法的实现...............................................................43

§5.3.3 贪婪挖掘算法的实现...............................................................44

§5.4 关键节点挖掘算法性能比较...............................................................46

§5.4.1 American College Football ........................................................ 47

§5.4.2 Neural Network ..........................................................................49

§5.4.3 Erdos991 .................................................................................... 50

§5.5 基于社区的关键节点挖掘算法...........................................................53

§5.5.1 算法的实验步骤与过程...........................................................54

§5.5.2 算法性能比较与结果分析.......................................................55

§5.6 本章小结...............................................................................................57

第六章总结与展望...................................................................................................58

参考文献.....................................................................................................................59

在读期间公开发表的论文和承担科研项目及取得成果.........................................62

致谢.........................................................................................................................63

第一章绪论

§1.1 研究背景

现实世界中，充满着各式各样的社会网络，例如，从大规模的电力网络到全

国的交通运输网络，从社会下层的人际关系网络到社会上层的政治、经济、科研

合作网络，从生态食物链网络到各种生物体内的新陈代谢网络等，可见，社会生

活中，社会网络无处不在。社会网络是由一群个体和个体之间的各种关系组成的

集合[1]，其中这些关系包括朋友关系、亲戚关系、上级与下级的关系、同学关系、

师生关系、同事关系、具有共同兴趣爱好的关系以及基于地域的邻居关系等。社

会网络可分为真实存在的社会网络和虚拟社会网络，真实存在的社会网络包括：

人际关系网、各种生态食物链网、公司内部的人事网、国家部门之间的业务网等；

虚拟社会网络包括：万维网、博客、论坛、MSN、Facebook、人人网、开心网等。

社会网络具有广泛的应用价值，其一，社会网络提供了许多新的交际方式，比如

在虚拟社会网络中，可以通过互联网来交友、分享信息、学习和找工作等；其二，

社会网络给商业带来了许多机遇与挑战，利用社会网络分析技术可以进行市场营

销，预防计算机病毒的传播，预测恐怖袭击，粉碎犯罪集团，进行疫苗接种等。

对社会网络分析技术的研究已有一定的历史积累，主要采用基于图论的分析

方法，研究成果有最早的小世界理论、中心性分析、社区分析以及有关社会网络

的度量标准等。近年来，随着计算机技术和互联网的迅猛发展，采用数据挖掘分

析方法对社会网络进行研究已成为一个热门的研究方向。基于图论的思想，把整

个社会网络表示成图的形式，其中，节点代表社会网络中的个体，边代表个体之

间的链接。因此，基于社会网络的数据挖掘分析方法[2]包括基于节点的分析（如：

关键节点挖掘、节点聚类以及节点的重要程度排序等）、基于链接的分析（如：链

接预测和链接发现等）、基于子图的分析（如：社区发现和子图分类等）。

在基于社会网络的数据挖掘方法研究方面，数据资源是非常关键的。然而，

互联网上海量的数据资源给这方面的研究提供了数据支持。研究人员可从许多渠

道来方便的获取大量的数据资源，例如，BBS，基于各类主题的论坛，天涯社区，

微博、银行数据、网上的购物数据以及电信数据等。

目前，在基于社会网络的数据挖掘方法研究方面，值得关注和研究的问题包

括以下三点：①与传统的数据挖掘方法不同，不仅要考虑单个个体，而且还要考

虑个体之间的链接、他们之间的拓扑结构以及相互作用等；②基于社会网络的研

究，所涉及的数据量非常庞大，虽然传统的社会网络分析方法已经比较成熟，但

基于社会网络的数据挖掘方法研究

是它只是基于小规模的数据量，对于大规模的数据量，还必须研究出新的方法；

③在数据挖掘的过程中，还涉及到用户隐私的问题，因此在使用数据时，要提出

保护用户隐私的解决方案。

§1.2 研究的目的及意义

在基于社会网络的数据挖掘方法中，社区发现方法和关键节点挖掘方法尤为

重要，既具有研究价值，又具有应用价值，在许多领域得到了广泛的应用。在商

业领域，可以先利用社区发现技术对某一城市进行社区挖掘，然后再利用核心节

点挖掘技术从每一社区挖掘出具有影响力的人物，最后有针对性地对这些关键人

物进行新产品的试用与广告，从而达到一传十、十传百的链式效应，得到事半功

倍的效果，打破传统投资回报率低的局面。在计算机网络安全防御领域，可以先

利用核心节点挖掘技术挖掘出那些容易传播病毒的关键计算机，然后集中注意力

对这些关键计算机进行重点防御，而不必盲目地花大成本来生产安全软件对整个

网络进行防御，从而达到投入少收益高的效果。公安机关打击犯罪集团时，通过

挖掘犯罪集团中的核心人物以及他们的联络人，就可以发现犯罪集团的重要头目

和中间联络人，从而能够迅速瓦解犯罪集团，所谓“擒贼先擒王”。

根据海豚的鼻音来对海豚群体进行分类，得到基于最短路径划分的社区结构，

如图 1-1 所示，它们被划分为两大类，分别用方框和圆圈表示，其中，圆圈表示的

类别又可以细分为三个小类，这个分类结果是根据 G-N 算法[3]得到的。通过对海

豚群体的正确分类，有助于海豚研究人员更深入的了解海豚群体。

图1-1 基于最短路径划分的社区结构

图1-2 可分为左右两个社区，其中节点 1和节点 3分别是左社区和右社区的关

键节点，而节点 2是左右两个社区的中介节点，在两个社区之间起到沟通交流的

作用，也算是该网络图的关键节点。若能发现并掌握一个社会网络图的关键节点，

第一章绪论

就能理解和掌握整个社会网络。

图1-2 社会网络的关键节点

因此，本文主要针对社区发现算法和关键节点挖掘算法展开研究与讨论。

§1.3 研究现状

在基于社会网络的数据挖掘方法研究方面，已经取得了一定的研究成果。国

内外学者提出了许多不同的社区发现算法，例如：K-L 算法[4]、谱平分法[5,6]、G-N

算法[3]、Radicchi 算法[7]等。在关键节点挖掘方面，也提出了不少的算法，例如：

NewGreedy 算法[8]、MixedGreedy 算法、DegreeDiscount 算法、HITS 算法[9,10]以及

PageRank 算法[11]等。

K-L 算法和谱平分法都是基于图分割的迭代二分法，Kernighan-Liu 算法根据

增益函数进行社区分割，而谱平分法根据拉普拉斯矩阵的第二小特征值对应的特

征向量进行社区分割，这两种算法都存在缺点，分别要求事先知道网络图分割之

后的社区大小和给定网络图包含的社区数目，这些条件限制了它们在社会网络分

析中的应用。Newman 等人提出基于边介数的 G-N 算法，每次去掉具有边介数最

大的边后，都要重新计算所有剩余边的边介数，该算法的时间复杂度为

)( 3

，不

适用于挖掘大规模的社会网络。于是，Newman 等人又提出基于模块度增量的快速

算法[12,13]，该算法是一种凝聚算法，每次合并使模块度增加最大的两个社区，算法

的效率非常高，适用于挖掘大型社会网络，因此本文将采用该算法进行改进。

Radicchi 算法是一种基于去边的分裂算法，根据具有最小边聚类系数的指标来去

边，该算法的时间复杂度也比较高，不适用于挖掘大型社会网络。

2009 年，在国际会议 ACM SIGKDD 上，Chen 等人提出 NewGreedy 算法和

MixedGreedy 算法，MixedGreedy 算法在 NewGreedy 算法的基础上进行改进，在

MixedGreedy 算法的第一轮采用 NewGreedy 算法，之后使用 CELF 算法[14]，经验

证，MixedGreedy 算法的性能确实得到了提高。之后，Chen 等人还提出了基于节

点度的 DegreeDiscount 算法，该算法是一种启发式算法，虽然该算法的运行速度

很快，但是准确度比较低，即以牺牲准确率来赢得时间。1999 年，基于 Web 链接

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要现实生活中存在着各式各样的社会网络，例如，人际关系网、万维网、博客、论坛、MSN、Facebook以及生态食物链网等。社会网络是由一群个体和个体之间的各种关系组成的集合，其中这些关系包括朋友关系、亲戚关系、上下级关系、师生关系以及网友关系等。对大型社会网络进行研究，从中挖掘出一些有价值的信息或模式，具有广泛的应用价值。其一，社会网络提供了许多新的交际方式，可以通过互联网进行交友、交流、分享信息、找工作等；其二，社会网络给各个领域带来了许多机遇与挑战，利用社会网络分析技术可以进行市场营销，预防计算机病毒的传播，预测恐怖袭击，粉碎犯罪集团以及进行疫苗接种等。本文主要针对社区发现算法和关键节点挖...

展开>> 收起<<

基于社会网络的数据挖掘方法研究.pdf

共65页,预览7页

还剩页未读，继续阅读

基于社会网络的数据挖掘方法研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: