1、文档名称 文档密级2019-7-17 华为保密信息,未经授权禁止扩散 第 1 页, 共 21 页浅析 Social Network和Graph Mining的应用和机器学习技术 - 吴斌 224227【摘要】随着移动互联网的到来，UCG（用户产生内容）的不断发展，社交网络（Social Network ）已经不断普及并深入人心，用户可以随时随地在网络上分享内容，由此产生了海量的用户数据，面对大数据时代的来临，复杂多变的Social Network数据是有很多实用价值有待挖掘的。本文通过对专家协作和主题的关系发现系统http:/arnetminer.org/ 和其相关的论文材料进行分析，讨论 S
2、ocial Network和Graph Mining 相关的机器学习技术, 为基于关系图谱的Social Network数据挖掘和应用提供一些思路。随着Facebook，Twitter，新浪微博，LinkedIn 等社交媒体网站的流行，对Social Network 的数据挖掘是近几年的一个技术热点，而Social Network中的用户与用户，用户与主题，用户与活动的关系网络就是一种图结构的海量数据，所以Social Network 的分析中一个主要方向就是针对关系图的Graph Mining。而针对Social Network 和Graph Mining，传统计算机技术面临很多挑战，比如，
3、图节点和边的数据已经达到数十亿的数据级别，海量图数据的分析计算和检索比较困难。而且，图数据结构是很复杂的，基于图结构的数据构建算法模型复杂度很高，比如，构建Social Network影响力传播的动态传播模型是很复杂的。还有，海量数据处理，势必带来并行化处理的要求，而图数据的关联性大，图数据分割复杂，导致基于图数据的分析算法并行化难度很大。面对这些挑战和困难，学术界已经有一些研究和实验，以下介绍的arnetminer系统的算法介绍，可以为基于图数据的Social Network和Graph Mining工作提供一些方法和思路。先来看一下，什么是图数据挖掘？图是一种很重要的数据结构，关于图数据的
4、数据挖掘有很多方向和应用领域，简介如下：文档名称 文档密级2019-7-17 华为保密信息,未经授权禁止扩散 第 2 页, 共 21 页纯理论的图数据挖掘中一个热点是频繁子图的数据挖掘（Frequent Subgraph Mining），即从图数据集合中寻找出现次数不少于最小支持度的子图。这个领域中有很多算法，AMG，FSG ，FFSM，gSpan， SUBDUE，GBI，SIGMAR ，GREW 等等。本文分析的是面向Social Network的图数据挖掘，主要关注的是社群发现（Community Detection），专家发现和排名（Ranking），结构洞分析（Structure Ho
5、le ），影响力分析（Influence Analysis），社交关系（Social Tie ），还有多种不同类型网络的数据集成等问题。首先，讨论一下Social Network数据挖掘的应用方式：1， 基于Social Network的意见传播，动态网络影响力传播分析。 举个例子：华为发布P6 手机后，需要做媒体宣传推广，假设领导给定100万预算，需要利用新浪微博做P6手机推广，那么市场人员最关心的问题就是，预计每个新浪博主的宣传费是1万元，怎么用这100万预算，在新浪微博上把P6 手机的推广做的效果最好? 具体化描述就是：基于新浪微博数据的用户Social Network中，需要找到Top
6、ic是“手机”相关的100个人（节点），这100个节点的影响力传播范围最大。这就是Social Network分析的典型应用之一，需要分析相关主题图结构数据中的“意见领袖”，“结构洞”（即跨越不同社群子网络的桥文档名称 文档密级2019-7-17 华为保密信息,未经授权禁止扩散 第 3 页, 共 21 页接节点），“动态网络影响力传播模型”等问题。类似的影响力传播图示：2， 领域专家发现，排名。举个例子：公司需要招聘数据挖掘方面的专家和牛人，招聘人员最关心的问题是，怎么找到学术界最有影响力的专家，以及这些专家擅长的学术课题，研究的技术方向，主要参加哪些学术会议，发表哪些论问题，合作者有哪些？
7、具体化描述就是：在某个学术主题Topic下，在相关论文，会议和作者构成的图数据中，找到专家的综合影响力分析排名,并找到专家与和合作者的关系，专家与研究课题,和相关学术会议的关系。（注：学术界专家评价有一个重要的参数是H-index 指数，H-index 指发表 N篇论文，每篇论文的引用数至少是N，他的H-index就是N。） 比如，数据挖掘领域专家排名：3， 社交关系分析。按照Social Network的六度空间理论，每两个人的关文档名称 文档密级2019-7-17 华为保密信息,未经授权禁止扩散 第 4 页, 共 21 页系一般只需要通过6个中间人就可以建立关系,所以社交媒体中，人们之间关
8、系基本都可以组成网络结构。社交关系分析，典型的应用案例是：通过用户的电话记录，或者邮件记录，分析哪些人是你的家人，哪些人是你的同事，谁是谁的领导等关系。比如下图：4， 相关主题的历史和趋势分析。 某个主题，他的描述表达方式，在不同的时间，会有很多表达方式，会有一些相关的子主题,这些不同的表达方式或子主题就是针对某个主题的一个Topic演进关系图。比如：与Deep Learning 相关的主题有Deep architecture，Deep belief network，Neural network， Feature selection，Reinforcement learning等，这些主题都与
9、Deep Learning 有着密切的关系，分析这些主题随着时间的变化可以看下图：5， 基于地理位置的某领域专家分布分析。比如，公司想做某个领域的研究，并建立相关主题的研究所，就需要分析，哪些地区，这个领文档名称 文档密级2019-7-17 华为保密信息,未经授权禁止扩散 第 5 页, 共 21 页域的专家有哪些。比如，下图中我们看到Deep Learning方面，全球顶尖专家的分布和介绍：6， 知识图谱的构建。知识图谱是Google，Baidu，Yahoo，SOSO等知名搜索引擎近几年新发展的技术。其核心是提供用户查询信息与相关知识的关系，直接通过图示的方法展现密切关联的信息，比仅仅提供网页
10、链接，对用户而言，价值要大很多。而且，信息的关联就是知识的直接体现. 所以，知识图谱被称作新一代的搜索引擎技术。 比如，某明星最近有哪些热点新闻，并且与哪些人有哪些关系等等。腾讯的SOSO华尔兹提供的明星社交图谱就是一个典型应用：文档名称 文档密级2019-7-17 华为保密信息,未经授权禁止扩散 第 6 页, 共 21 页实际上，各大通信运营商已经开始关注社交网络的数据挖掘和应用。比如，中国移动已经在规划基于VGOP分析构建用户关系网，简介如下：文档名称 文档密级2019-7-17 华为保密信息,未经授权禁止扩散 第 7 页, 共 21 页通过以上的介绍，我们可以知道Social Netwo
11、rk和Graph Mining的实用价值和应用场景。然后，我根据专家协作和主题的关系发现系统http:/arnetminer.org/，具体分析 Social Network和Graph Mining的相关技术。该系统是清华的唐杰老师带领团队研发的针对学术专家研究分析的系统，唐杰老师是Social Network 领域学术界的大牛，这里可以看到Social Network领域学术界的专家和发展趋势：文档名称 文档密级2019-7-17 华为保密信息,未经授权禁止扩散 第 8 页, 共 21 页文档名称 文档密级2019-7-17 华为保密信息,未经授权禁止扩散 第 9 页, 共 21 页Arn
12、etminer系统是以学术论文为主要数据，进行专家排名，关系挖掘，学术主题相关性发现，历史趋势分析等课题进行研究的公开网站，上面的这些图就是该网站上截取的内容。该系统与华为公司有合作项目。唐杰老师有一个PPT“Computational Models for Social Networks”，对 Social Network的模型，算法和应用做了一个全面的总结，网上可以下载：http:/ Finding in A Social NetworkJing Zhang, Jie Tang, and Juanzi LiDASFAA2007，主要是对领域专家发现排名系统的模型算法进行说明。2）Topic
13、 level expertise search over heterogeneous networksJie Tang Jing Zhang Ruoming Jin Zi Yang Keke Cai Li Zhang Zhong SuMLJ2011， 主要是ArnetMiner系统构建和查询的模型进行详细说明，这篇论文很长，介绍很全面。3）ArnetMiner: Extraction and Mining of Academic Social NetworksJie Tang, Jing Zhang，Limin Yao, Juanzi Li ，Li Zhang, Zhong Su文档名称 文档
14、密级2019-7-17 华为保密信息,未经授权禁止扩散 第 10 页, 共 21 页KDD2008，主要是对于学术领域，ArnetMiner系统的信息抽取，名称消歧，数据集成等的模型和架构，ACT模型详细说明。与上一篇论文不同的是，上一篇很全面，这一片很详细，对核心的关系构建模型ACT，有详细的说明。4）Inferring Social Ties across Heterogenous NetworksJie Tang，Tiancheng Lou，Jon KleinbergWSDM2012，主要是从不同类型的多个网络中，对用户信息进行集成Transfer学习。5）Social Influenc
15、e Analysis in Large-scale NetworksJie Tang，Jimeng Sun ，Chi Wang and Zi YangKDD2009，主要是对网络节点影响力评估模型TAP进行详细说明。6）Social Action Tracking via Noise Tolerant Time-varying Factor GraphsChenhao Tan, Jie Tang, Jimeng Sun, Quan Lin and Fengjiao WangKDD2010，主要是针对基于时间段的网络影响力活动动态传播模型NTT-FGM进行详细说明。7) Learning to
16、Infer Social Ties in Large NetworksWenbin Tang, Honglei Zhuang, and Jie TangKDD2011,主要是使用半监督学习的方法进行自动添加关系label的模型PLP_FGM详细说明。8）SAE: Social Analytic Engine for Large NetworksYang Yang, Jianfei Wang, Yutao Zhang, Wei Chen, Jing Zhang, Honglei Zhuang,Zhilin Yang, Bo Ma, Zhanpeng Fang, Sen Wu, Xiaoxiao Li, Debing Liu, and Jie TangKDD2013，主要是对ArnetMiner的新版本SAE平台框架进行说明，数据集成方面比较详细。同时，以上资料中还有介绍大规模分布式图数据挖掘的并行算法介绍。其他参考资料：THUKEG-SAE-D1-1 ，THUKEG-SAE-D3-12，THUKEG-SAE-C1-C2，THUKEG-SAE-B2等，不一一列举。ArnetMiner（即 SAE）总体架构可以看以下几张图：
