LinkedIn 职业网络中的数据挖掘应用
曹海洋 季小俊
摘要：近年来，社交网络发展迅速，各种社交的网络平台每天都会产生海量的用户数据。这些无序的数据中隐藏着潜在的价值，也为研究者提供了用数据挖掘中的方法来分析这些数据的机会。聚类是数据挖掘中的一个基本技术，而利用聚类方法我们能够实现LinkedIn职业网络中的数据挖掘。
关键词：社交网络；数据挖掘；应用；聚类；LinkedIn职业网络
中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）13-0001-02
Abstract：In recent years， with the rapid development of social network， the different social networking sites produce large amounts of user data every day. There is potential value in these disordered data. It also provides researchers with opportunity of using data mining methods to analyze these data. Clustering is an essential data mining techniques， and we can achieve data mining in LinkedIn professional network with the use of clustering method.
Key words： social network； data mining； application； clustering； linkedin professional network
社交网络，顾名思义是用于社交的网络平台，它最初是以交友为开端的，在社会的不断发展中逐渐演变成了今天的集社交、通讯、娱乐、商业等元素为一体的多元化平台。基于网络的社会交往诞生于早期的基于终端的计算机，以及通过新闻组或其他早期的互联网软件来进行。社交网络的新时代开始于互联网的性能的上升，以及万维网（Web）的逐渐占据主导地位。
近年来，国内的新浪微博、人人网，国外的Facebook、Twitter和LinkedIn等社交网站，也已经从时尚变为主流。而社交网络的爆发之所以能在最近几年爆发，很大程度上是由于社交网络和媒体共享网站提供了大量的用户数据。而如何对这些海量数据进行高效的分析和处理，也决定了社交网络今后的发展。
1 社交网络数据分析概述
网络和信息技术的飞速发展使得社交网络成为人们生活中不可缺少的一部分。网络设计采用电子邮件作为一个起点，而不是实际生活中的信件。然后开心网，BBS等网站，是由它演变，并且以虚拟为其主要特色。在社交网络演进的过程中，个人的形象由实际生活中的具体个人转化为一个虚拟形象。所有的这一切都归功于社交网络的诞生，然后又驱使人们提出网络扩展和降低成本的特征之间的联系。良好的社交网络数据分析技术可以在社交网络的爆炸式发展的过程中为用户们创建一个积极乐观的网络环境和氛围。
流行的社交网络如今被认为是社交加网络，即通过将网络作为载体，将很多的用户连接以形成具有一定特性的虚拟社区。和基础科学不同，对社交网络的数据分析重点是人与人之间的相互联系[1]，而不仅仅是独立个体的属性。社交网络分析就是研究这种社会结构的，它主要检查关系之间的结构和组成，并分析其结构特点[2]。通常包括：
1）个体的邻接点之间是如何连接的；
2）彼此之间经常进行通信的个体[3]（社区）；
3）通过网络传递信息所涉及的个体数[4]（路径长度）；
4）实际网络中可能存在的关系的比重[5]（密度）。
2 数据挖掘在社交网络中的具体应用——LinkedIn中的职业网络聚类
2.1 LinkedIn中数据挖掘的意义
LinkedIn是全球最大的职业社交网站，它主要关注用户的职业和相互之间的商业关系，即“人脉”。LinkedIn的理想定位为年轻职业人员，被广泛地用于构建和维护外部职业网络。因为LinkedIn的管理团队认为用户的职业数据本质上是私有的，并且这些数据非常宝贵，不能像Facebook或Twitte上的好友那样任意查看。由于这类数据的敏感性，LinkedIn中API提供的数据和一般社交网站是有本质区别的[6]。LinkedIn限制用户访问自己“一度人脉”的某些信息，因此它不适用于作为图挖掘。本章下面的内容将介绍如何用基本的聚类分析来帮助用户找到以下几个问题的答案：
1）你的哪些“人脉”和你的职位最相似？
2）你的哪些“人脉”曾在想去的公司工作过？
3）你的大多数“人脉”住在什么地方？
2.2 使用聚类分析的动机
聚类分析可以作为一个单独的工具被用以发现数据库中分布的一些深层的信息，然后归纳出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析[7]。对于LinkedIn的大量数据，在实现上一节中提到的数据挖掘时，我们会遇到两个问题：
对于职位、公司名称、专业领域等字段，如何合理度量两个字符串之间的相似性。
如何用时间复杂度较小的算法将所有的项用一个相似性度量聚合成一个集合。
上述两个问题也是聚类分析中通常会涉及的问题，因此可以按职位将联系人聚类来实现LinkedIn中的数据挖掘。
2.3 聚类分析的具体过程
2.3.1 规范职位名称和统计职位数量
在使用LinkedIn数据集时，先要导出一定数量的联系人。由于职位之间的细微差别也可能对数据挖掘结果产生巨大的影响，因此在处理这些数据之前，先通过用已知缩写来替换同义的职位（如“总裁”和“CEO”）来标准化常见的职位，再通过编码计算这些职位出现的频率。这里得到的频率分布的结果只是针对职位中的全职称和个别标记，但仍可以作为后面数据分析的起始模板。
2.3.2 对职位的相似性度量
在获取一组表示职位的字符串并以一种有效的方法将他们聚类时，面临最大的问题是使用哪种基本的相似性度量[8]。对字符串的相似性度量在很大程度上取决于目标的性质。而在比较职位时，可能会使用如下的几种常见的相似性度量：
l 编辑距离
编辑距离是一种简单的度量，它用于记录将一个字符串转换成另一个字符串时，需要插入、删除或替换的次数[9]。例如，将“bed”转换成“bad”需要一次替换操作，编辑距离为1。对于长度为K和P的字符串来说，计算编辑距离的时间复杂度为O（K*P）。
l N元语法相似度
N元语法可以简单的表示文本中n个标记的所有可能的连续序列，它提供了计算不同排列的基本数据结构[10]。N元语法相似度有很多变化，考虑最简单的情况：计算两个字符串标记中所有可能的二元语法，通过统计两个字符串之间共同的二元语法来计算它们之间的相似度。
l MASI距离
MASI距离度量是雅克比相似度的加权版本[11-12]，当集合之间存在部分重叠时，它通过调整得分来生产小于雅克比相似度的距离。MASI距离的测量方式如1所示：
1 -float（len（X.intersection（Y）））/float（max（len（X），len（Y））） （1）
其中，X和Y表示项集。需要注意的是，当两个集合完全不相交或相等时，MASI距离和雅克比距离相同；当两个集合部分重合时，MASI距离大于雅克比距离。针对表示职位的字符串，显然符合后一种情况，因此这里使用MASI距离会更高效。
3 使用贪心启发来聚类职位
本节介绍如何将职位聚类，并用MASI距离与其他职位相对比。这里，用编码从常见的连词列表分离出综合职位，并标准化常见职位。然后嵌套循环遍历所有的职位，并根据一个阈值MASI相似性度量将它们聚类。如果相似性启发确定的任意两个职位的距离足够近，就可以“贪婪”地将它们聚合起来。在此基础上，“贪婪”意味着第一次就能确定一个可能适合某一聚类的项，继续前进并对其分配，而不需要考虑是否有更合适的选择[9]。
然后，用编码根据特定的职位查询联系人，并将结果分组显示。结果的可视化效果如图1所示：
3.1从地理上聚类网络
本节将介绍如何使用Google Earth标识LinkedIn职业网络。为了实现聚类在Google Earth上的可视化，第一步先要从每个联系人的公开资料中解析出地理位置，然后根据地理编码器将位置编码到坐标中。接着把地理坐标提供给聚类模块来计算聚类，这里会按地址将联系人分组，将他们聚类，然后用聚类的结果计算质心。由此，我们可以得出“人脉”住在哪里的答案。
以LinkedIn为代表的社交网络软件在我们研究的问题中被大量使用。本章介绍了基本的聚类技术，并通过各种方式将它们应用到LinkedIn职业网络的数据中，以此来找到关于“人脉”的几个问题的答案，并且整个数据挖掘的过场快速高效，交互方式友好，为用户的职业网络管理提供了一种全新的体验。通过这几个LinkedIn职业网络中的实例，我们可以了解到数据挖掘在社交网络中的具体应用。
4 结束语
本文简要地介绍了社交网络中的数据挖掘应用的意义。并通过一个具体的实例——用聚类方法实现的LinkedIn职业网络的数据挖掘来介绍社交网络中数据挖掘的大致方法和过程。除此之外，我们还能用其他的数据挖掘方法，对各种社交网络的数据进行高效的分析和处理，以满足用户在使用社交网络过程中的各种需求。
参考文献：
[1] Calvani A， Fini A， Molino M， et al. Visualizing and monitoring effective interactions in online collaborative groups[J]. British Journal of Educational Technology， 2010， 41（2）：213-226.
[2] Limited B P. British Journal of Educational Technology[J]. British Journal of Educational Technology， 2009， 35（3）：275-288. （下转第5页）
（上接第2页）
[3] Chen J， Fagnan J， Goebel R， et al. Meerkat： Community mining with dynamic social networks[C]. In Data Mining Workshops （ICDMW）， 2010 IEEE International Conference on， 2010： 1377-1380.
[4] Artz D， Gil Y. A survey of trust in computer science and the Semantic Web[J]. Web Semantics Science Services & Agents on the World Wide Web， 2007， 5（2）：58-71.
[5] Rodgers R J， Halford J C G， Souza R L N D， et al. SB-334867， a selective orexin-1 receptor antagonist， enhances behavioural satiety and blocks the hyperphagic effect of orexin-A in rats[J]. Annals of Oncology Official Journal of the European Society for Medical Oncology， 2001， 13（7）：1444–1452.
[6] Backstrom L， Leskovec J. Supervised random walks： predicting and recommending links in social networks[C]// ACM International Conference on Web Search & Data Mining. ACM， 2010：635-644.
[7] Marco A D， Navigli R. Clustering Web Search Results with Maximum Spanning Trees[J]. Lecture Notes in Computer Science， 2010， 6934：201-212.
[8] Cho H， Gay G， Davidson B， et al. Social networks， communication styles， and learning performance in a CSCL community[J]. Computers & Education， 2007， 49（2）：309-329.
[9] Clauset A， Newman M E J， Moore C. Finding community structure in very large networks. Phys Rev E 70（6）：066111[J]. Physical Review E， 2005， 70（6 Pt 2）.
[10] Tang J， Hu X， Liu H. Social recommendation： a review[J]. Social Network Analysis & Mining， 2013， 3（4）：1113-1133.
[11] Agarwal N， Liu H， Tang L， et al. Modeling blogger influence in a community[J]. Social Network Analysis & Mining， 2011， 2（2）：139-162.
[12] Aral S， Muchnik L， Sundararajan A. Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks. Proc Natl Acad Sci[J]. Proceedings of the National Academy of Sciences， 2009， 106（51）：21544-9.
