基于项目合作的社会关系网络构建-何贤芒.pdf

《基于项目合作的社会关系网络构建-何贤芒.pdf》由会员分享，可在线阅读，更多相关《基于项目合作的社会关系网络构建-何贤芒.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机研究与发展DOI：107544issnl00012392016201 51172Journal of Computer Research and Development 53(4)：776784，2016基于项目合作的社会关系网络构建何贤芒h 4 陈银冬2 李 东3 郝艳妮31(宁波大学信息科学与工程学院浙江宁波315211)2(汕头大学工学院 广东汕头 515063)3(国家自然科学基金委员会信息中心 北京 100085)4(复旦大学计算机科学技术学院 上海 200433)(hexianmangnbueducn)A Construction for Social Network on

2、the Basis of Proj ect CooperationHe Xianman91一，Chen Yindon92，Li Don93，and Hao Yanni31(Facult了of Information Science and Engineering，Ningbo University，Ningbo，Zhejiang 315211)2(College of EngineeringShantou University，Shantou，Guangdong 515063)3(Information Center，National Natural Science Foundation of

3、 China，Beijing 100085)4(School of Computer Science，Fudan University，Shanghai 200433)Abstract For the time being，the social network based on paper cooperation has gained a great deal ofattention，but there exists inaccurate entity recognition，failing to update data in time，and uncertaindata quality et

4、c In view of this，this paper puts forward the cooperation on the basis of the historyproject application，and the problem of the entity recognition attributes to a clustering problemThecomDutational complexity of the problem is provedThen the algorithm is proposed to settle theproblemFinally，the effi

5、ciency of the algorithm is verified by the experiments on real dataKey words project cooperation；social network；entity recognition；clustering；computatlonal geometrYproblems摘要 目前，基于论文合作关系的科学研究人员社会关系网络得到了极大的关注，但是存在实体识别不准确、数据更新不及时等数据质量问题有鉴于此，提出利用历年项目申请书的合作关系，同时将实体识别问题归结为一个聚类问题，证明该问题的计算复杂度，然后提出了算法来解决该问题

6、，最后在真实数据上验证算法的效率关键词 项目合作；社会关系网络；实体识别；聚类；计算几何问题中图法分类号TP31113l收稿日期：2015一1221；修回日期：201603 11基金项目：国家自然科学基金项目(61103244，U1509213)；广东省自然科学基金项目(201 5A030313433)；广东省高等学校优秀青年教师培养计划项目(Yq2013074)；广东省普通高校特色创新项目(2015KTSCX036)；广东省高校工程技术研究中心建设项目(GCZXA1306)；信息与通信工程浙汀省重中之重学科开放基金项目；中国博士后科学基金项目(2013M540323)；教育部人文社会科学研究

7、项目(1 5YJA630069)；汕头市科技计划项目(98)This work was supported by the National Natural Science Foundation of China(61103244，U1509213)，the Natural ScienceFoundation of Guangd。ng Province of China(2015A030313433)， the Foundation for Distinguished Young Talents in HigherEdueation of Guarlgdong(Yq2013074)，the Ch

8、aracteristic Innovation Project in Higher Education of Gua“gdo“g(201 5KTSCX036)the Engineering and Technology Research Center of Guangdong Higher Education Institutes(GCZX A1306)，the Top Pri。rity of the DiscipIine(Information and Communication Engineering) Open Foundation of Zhejiang，the ChinaPostdo

9、ctoral Seience Foundation(2013M540323)，the Humanity and Social Science Foundation of Ministry of Education of China(1 5YJA630069)，and the Shantou Science and Technology Foundation(98)通信作者：陈银冬(ydchenstueducn)万方数据何贤芒等：基于项目合作的社会关系网络构建 777由于社交网络的繁荣发展和广泛应用，越来越多的研究者将其科学研究和应用开发的注意力集中到社会网络这种虚拟世界当中社会网络分析已然成为

10、社会学、地理学、经济学、信息科学等诸多学科的重要研究内容，其研究涉及了数据挖掘、知识管理、数据可视化、统计分析、社会资本、小世界理论、信息传播等多个学科基于社会关系网络数据进行数据挖掘和潜在模式分析比传统数据统计分析更加科学、效果更好、应用前景更突出，通过对社会网络进行挖掘可以获得比简单实体数据更详实(如实体在社会网络中的关系)、更准确(如挖掘实体间的关系)的信息目前国内已有的基础研究人员社会关系网络主要是基于论文合作关系的信息服务平台，具有代表性的工作有深圳爱瑞斯公司研发的科研之友u J、清华大学知识工程库开发的ArnetMiner21、CCF学术空间(仅限计算机领域的合作关系)E3、中国人

11、民大学研发的学术空间ScholarSpace4一等这些平台共同的特点是提供了针对网络中海量文献检索服务，同时从作者、期刊会议、工作单位、学科领域、合作者关系等多个角度进行统计与分析，还挖掘出基于论文合作的合作关系但是上述平台的数据主要抽取网络中的不确定性数据，存在数据来源多样化、格式不一致、数据不准确、更新不及时等数据质量问题，导致实体识别不准确本文的研究动机有如下2个：1)张冠李戴在实践中，作者中文姓名重复的现象非常普遍比如中文名“张伟”，我们对CNKI数据库经过专门的实体识别后发现，存在460多个张伟对这众多似是而非模棱两可的“张伟”，哪怕采用人工尚有不小难度，更何况是计算机呢?“张伟现象

12、”的根本原因在于从论文中提取的信息太少，只包括姓名、单位、邮箱、期刊名、论文共同作者等有限信息，而且在关于邮箱信息上往往也只有通信作者的邮箱(如果考虑到格式问题，很多作者的邮箱也不完整)。因此，基于论文合作的社会关系网络的构建，即使考虑领域信息和共同合作关系，也无法做到准确的识别“张伟现象”仅仅是以论文合作社会关系网络的构建中的一个普通案例事实上，我们在尝试构建3 000多位国家杰出青年基金获得者的社会关系网络时，依然存在识别准确性不高的现象，特别是论文与作者问张冠李戴的现象相当突出因此，基于论文合作的社会关系网络难以做到对实体的准确识别2)项目合作论文和项目都是科研工作者最主要的科研成果形式

13、，也自然是科研合作最常见的表现形式既然基于论文合作构建社会关系网络比较困难，那么是否可以基于项目合作来构建社会关系网络呢?通过项目共同参与申请，将实体联系成一个复杂的社会关系网络在社会关系网络中，每一个实体都是一个顶点，同一申请书中的申请人A与参与者B之间存在有向边：BA，其他参与者之间没有边关联由于申请人也往往是其他项目中的参与者，如此便构成了一个复杂的社会关系网络以国家自然科学基金委员会(简称基金委)每年接收的申请书为例，目前已累积1000多万条申请人与参与人的信息，这些申请者的信息包括姓名、性别、单位、邮箱、身份证号、出生日期、职称、申请人参与者等通过对真实数据分析发现，绝大多数信息都是

14、完整准确的需要强调的是：同一实体在不同申请书中的信息有可能并非完全一致比如由于工作调动而导致单位、邮箱等信息的变化而更加特别的现象是，部分实体基于某些原因(比如规避基金委的申请限项规定)而故意错误填写某些关键信息(比如身份证号码)表1给出了项目申请书合作关系的一个示例其中，id，prp code，name，sex，org name，Table 1 An Example of Cooperation in Project Application表1项目申请书合作关系示例万方数据778 计算机研究与发展2016，53(4)birthday，email，ispc，cardcode等字段分别表示元组序

15、号、项目受理号、姓名、性别、单位、出生日期、邮箱、是否项目负责人、身份证号等基于隐私保护考虑，已对身份证号进行了替换处理在通过手工整理与实体识别处理后发现：基于项目合作的社会关系网络关系准确、可靠性高，为科学基金项目管理提供辅助检索与查询，保证科学基金的公正与公平，具有重要的研究价值和现实需求本文的主要工作包括3个方面：1)提出了一个基于项目合作的社会关系网络的构建设想，并从中发现一个重要现象：3个属性值相同的元组可以认定为同一实体，从而引出本文讨论的主要问题2)研究求解该问题的计算复杂度通过证明该问题等价于计算几何中的USEC问题，说明该问题的计算复杂度的下界满足n(托刮3)，除非USEC问

16、题和Hopcroft问题在算法理论上有重大突破3)利用数据聚类方法构建一个基于项目合作的社会关系网络，并提出高效的解决算法，同时基于真实数据对算法运行效率进行了验证1基本概念与问题定义给定一个数据集丁(A。，A。，A。)，假定T共有d个属性，用tEA，表示其属性值，数据集中的一个点称为对象定义1一邻域B(多，)给定对象多，其半径e内的区域称为该对象的s一邻域定义2核心对象(core point)如果给定对象e-邻域B(声，e)内的样本点数大于等于MinPts，则称该对象为核心对象，其中参数MinPts是一个预先给定的正整数定义3密度可达对于数据集T，如果存在一个对象链P。一q，P：，P s，P

17、t，PtP，其中P，P2，P女，是核心对象，且p：一-B(P：，)，i一1，2，k一1，则称q密度可达P例1图1给出一个密度可达的示例此时Mi，IPs一3，P，密度可达P。，对象链是P，Pc，Pj，但Pj并非核心对象在数据整理的实践过程中，我们发现了重要现象(以下统称为“三属性现象”)：观察1申请人数据库中，在性别相同的情况下，任何2条元组只要在姓名、单位、邮箱、身份证、出生日期等5个主要属性上有3个以上的值相同，00 凡Pl o尸2P4Fig1 An example for MinPts：3图1 MinPts：3的示例图可认定为同一实体根据“三属性现象”，在表1中，元组t，tj，t。，t。可

18、认定为同一实体，元组t2，t3，6也可认定为同一实体，而对元组t，则无法确定其是否与元组t。，t。，。为同一实体此外，对于一些明显错误的证件号码比如123456，2222222，00000000等进行去除操作，同时注意到2个不同的申请人伪造了相同的证件号码可能性是很低的，比如表1中的证件号码000000123456789012，尽管是错误的，但仍然有参考价值定义43一属性值相同(3-attribute valuesame)任取数据集T中2条元组t，t。E T，如果存在至少3个属性值相同，便认定为同一实体定义5距离2个元组t1，t2的距离dist(tl，t2)定义如下：一f 1，J i：1id，

19、t】EA：一t。A。J3；出“1嘞户10，id,tl EA：一。A，I3，按照上述类和距离的定义，将数据集T分成不同的类2聚类问题的计算复杂度首先给出2个计算几何问题和若干已经证明的相关结论21 2个计算几何问题定义8USEC问题给定一些半径r相同的球集合5叫和点集S判断是否存在某个点PS，P在某个球内其中，点和球均为d维数据，d是常数定义9Hopcroft问题给定2一D空间上的点集S。和一些线S嘶。，判断是否存在某些点PE S叫P在S。的某些线上定义10Hopcroft困难问题口】如果问题X可以在()(引3)内解决，表明存在算法在o(n刮3)内解决Hopcroft问题，那么问题X是Hopcr

20、oft困难问题换句话说，如果Hopcroft问题能在n(押4加)时间内解决，那么问题X也存在同样时间复杂度的算法设卵一f S。f+l S川I，当d一3时，USEC问题可以在O(九log)副3)内解决，而寻找时间复杂度O(n 43)的算法依然是公开难问题类似地，设九一S。l+J S。I，研究认为Hopcroft问题的时间复杂度是n(册叫3)，而对于USEC问题则有结果：引理16当d5时，USEC问题是Hopcroft难问题2个计算几何问题的示意图如图2所示：o(b)HopcroftFig2 TWO computational geometry problems图2 2个计算几何问题22计算复杂度

21、下面证明问题1与USEC问题等价，进而说明其与DBSCAN问题等价定理1当d4时，问题1与USEC问题等价证明对于任意维数矗4，如果我们能在厂(行)时间内解决问题1，那么就可以在厂(钾)+0(以)时间内解决USEC问题考虑到USEC问题是定义犁空间上的S。点集和半径相同的S BaIt球集合设算法A能在，(朋)内完成问题1我们设计一个算法1在f(行)+0(”)时间内回答USEC问题，行=S，l+|S叫 证毕算法1USEC问题回答算法记5。，的球心集合为S。，设数据集PS。：U5。刚球半i芑一l；在数据集上运行算法A；如果存在某个点PS。和P 7S。，在同一个类中，那么回答Yes；否则回答No显然

22、，算法l的执行时间不超过厂(理)+o(门)，下面分2种情形证明其正确性情形1回答Yes情形首先注意到如果把一个类里面的点作为顶点，若顶点问距离为l则用边连接，那么在同一个类中的点便构成一个连通图若P，P 7处于同一个类中，则存在一个对象链：P。一P，Pz，P。，P；，P。一P 7，从而，一定存在P。，PH使得P，SPS。考虑到P。B(pH，)，从而球覆盖了点Pi。情形2回答No情形相反地，如果P和P并非处于同一类中，那么二者之间的距离为0，故不存在某个P：属于P 7的一邻域B(P，)，因此回答是No定理2当d4时，问题1与BSCAN问题等价Tao等人_3证明了DBSCAN算法与USEC问题定价

23、结合定理1，定理2的结论不言而喻事实上，问题1与DBSCAN问题的等价性是明显的，只需巧妙设置DBSCAN问题中的2个参数(Minpts一1，一1)即可此时，Minpts一1意味着DBSCAN里面所有点都是核心对象综上，本文得到问题1的计算复杂度的结论如下：当d4时，问题1与USEC问题和DBSCAN算法均等价。当d一4时，问题1需要在f(九4邝)时间内解决，除非USEC问题可以在0(，24邝)解决当d5时，问题1是Hopcroft难问题，亦即问题1需要在22(”射。)时间内解决，除非USEC问题可以在()(”“3)内解决3 相关工作目前社会关系网络研究中最受关注的是，除了基于论文合作的社会关

24、系网络外，还有基于论文万方数据780 计算机研究与发展2016，53(4)引用的社会关系网络8、基于电话的社会关系网络L9J、基于关注的社会关系网络(比如Twitter、微博)n 0I、基于专利合作的社会关系网络n妇等同时，也有一些相应研究与具体应用现在，已有超过20多个社会关系数据集发布于网上供公众研究与测试对于社会关系网络的研究分析主要包括3个方面：1)社会影响分析与行为分析主要包括网络上节点与边的影响力分析、节点与边的度量、节点介数等123Kumar1胡研究了网站上博客信息动态传递行为、应用传染病机制来对主题传播行为进行建模Gruhl等人口4探索了社会网络会话结构的形成，并用一种数学模型

25、来刻画用户对话行为文献15研究了社会关系网络中强连接节点问题LibenNowell和Kleinberg16一探讨了人与人之间信息传播过程来重构大规模分发互联网连锁信的传播机制，他们发现连锁信通过一种很窄且很深像树一样的模式传播Yang等人L1 71分析了Twitter上用户转发行为，并提出了一个半监督的框架来预测用户的行为；Myers等人口胡研究了消息的扩散过程是如何受外来消息源的影响；文献19提出了一个SPIKEM模型来表示消息传递的上升与下降模式Huangr20!研究了社会关系网络中的群体形成问题尤其是triad形成问题，并建立一个模型来在线预测动态社会关系网络中closed triad的

26、形成2)社会关系分析Tang等人21研究了异构网络环境下如何区分不同类型的社会关系，提出了一个整合了社会关系理论框架，可以有效地提升社会关系类型的区分Wang等人【221提出了一种挖掘导师与学生关系的TPFG模型，该模型以论文合作的社会关系作为研究对象文献1-23提出了一个监督随机游走算法来估计关系中的强度，Diehl等人24 o提出了一个排名函数来区别上下级关系文献e52提出了移动通话数据中的几种关系模式，并利用这些模式来推断朋友关系网络Sun等人2刚研究了多个类型动态网络中社区演化3)社会网络结构分析Yang等人1 7研究了社会关系网络的用户转发行为；Zhang等人。27发现社会关系网络的

27、局部性，也就是一个人容易受到其最亲密的朋友影响，形式化表述了这个现象并建立数学模型来预测用户的转发行为结构洞(structural holes)理论m1也在社会关系网络结构分析中得到了应用，文献29研究了社会关系网络的结构洞形成问题，Lou等人m1描述了如何挖掘大型社会关系网络的结构洞中top-k问题，并证明了该问题是NP-hard此外，关于DBSCAN算法的研究，最早是由Ester，Kriegel，Sander和Xu在KDDl996会议r3】上提出，一经提出就受到了极大的关注值得一提的是，DBSCAN算法的提出者一直误以为其时问复杂度为O(n log门)，直到2013年才由Gunawan。2

28、0指出其实际时间复杂度是O(-2)，陶宇飞等人71在2015年SIGMOD会议上证明了DBSCAN算法的时间复杂度：当数据维度是d一3或d一4时，DBSCAN算法与USEC问题等价；当d5时，是Hopcroft难问题；同时，他们还提出了一个时间复杂度为0(订)的近似算法特别地，对于2维数据，Han等人3胡提出了时间复杂度为O(卵log竹)的算法，同时证明了类的数量正好等于图的连通分量的数量此外，对于Hopcroft问题，目前最好算法的时间复杂度大致比O(n43)稍大，具体可参阅文献344实体识别算法在本节，我们将提出实体识别算法，即问题1的求解算法由第2节的讨论可知，问题1的计算复杂度下界是n

29、(钾们)，除非USEC问题与Hopcroft问题有了重大的理论突破，因此直接设计时间复杂度为o(订log挖)不太现实此外，注意到近似算法对问题1没有特别的意义，因此本节算法的设计是精确(exact)算法根据观察得出的结论，对数据集T采用交叉比对的方法进行实体识别算法2给出了一个初等的Naive算法，该算法的时间复杂度o(竹2)，11为数据集丁的大小42节将提出一个改进算法41基于规则的Naive算法算法2基于规则的Naive交叉比对算法输人：数据集丁；输出：类C，C。，Cfor i一1 tO丁 for ji+1 to TI if(dist(t。，t，)一1)*如果3个属性值相同* 将t和t，标

30、记为同一个类； end if end forend for按顺序输出每个类及其所包含的元组算法2的直接想法是检查每对元组是否满足3一属性值相同，若相同就标记为同一实体，并放入同一类中算法2虽然复杂度较高，但算法简单，可作为基准算法和检验后续算法的准确性万方数据何贤芒等：基于项目合作的社会关系网络构建 78142基于分组的改进识别算法对于大数据集，时间复杂度为0(”2)的算法2几乎是不可接受的，因此需要改进算法问题1的本质是找出所有至少3个属性值相同的类C，C：，C。我们可以先找出某一个属性值相同的集合T，T：，T。)，然后对每个T。进行交叉比对，从中找出并确定类C，C，C。，以上便是算法3的基

31、本思想为了解决问题l，算法3至多运行d一2次，记录每次算法的结果Cn，C，c，设元组t每次落在不同的类C，C。一，C。叫；，将这些类合并为一个类，当所有的元组都完成合并时，算法便终止算法3基于分组的识别算法输入：数据集T、丁的某属性Attr；输出：类C，C，C，。以属性Attr为主进行排序；将丁划分为丁。，L，瓦，使得丁一T，UT：UU瓦，T：n丁，一；对每个丁。进行交叉比对；for i一1 to f丁。f for歹一i+1 to T。l if(dist(f，t，)一1) 将，和t，标记为同一个类； end if end forend for按顺序输出每个类及其所包含的元组算法4是针对上述“合

32、并”操作的算法，其基本思想是对于每个元组t，找出其落在2次不同分组的类C。，C：，计算差集C。C，如果差集C，一C：是空集，说明元组t前后2次不同的聚类后的结果相同，此时不需要进行合并；如果差集C，一C：非空，那么说明元组t前后2次不同的聚类分在不同的类中，因此需要将类c，C。合并算法3的时间复杂度等于O(nlog+芝：f E 2)，r：l因此，其算法的效率主要依赖于属性A，分组丁，的大小如果丁。都比较小，其时间复杂近似等于0(胛log，z)；如果某个丁：比较大，那么近似等于”2，因此算法2的时间复杂度下界是12(理log靠)合并算n J 3法的时间复杂度上界是(C：，logC：，)f=1 5

33、=1算法4合并算法输入：2个聚类结果z，和l。；输出：分组集合z，for i一1 to TI 设t；在2次聚类z，和l。的分组分别是C、和C2； C，一C：一C，；*2个分组的集合差集* if C：一*前后2次聚类结果相同* continue； else*前后2次的聚类结果不同，需要合并*| 对C，中的每个元组t merge(C1，Cj)*C是t在l】中所在的类* end ifend for5数据实验报告51数据预处理在申请人的数据库中，发现有些申请书的某些数据是故意填写错误，比如不存在的证件号码、依托单位信息变更、不符合规则的电子邮件等预处理主要任务是去除这些不规范(甚至错误)的申请人数据具

34、体做法是人工筛选出明确错误的数据共30 621条，直接将其从数据测试集中去掉用于测试的数据集是从国家基金委1986-2014年的申请书中提取的合作关系，共计9840477条数据，其中性别为男和女的2个数据集各有6 092 060条和3 748 417条每条元组含8个属性(项目编号、姓名、单位、邮箱、性别、是否主持人、证件号码、出生日期)为了防止信息的泄露，所有的数据通过AES加密，相同的数据加密后依然相同，因此加密后的数据对算法没有影响为了测试算法的可扩展性，又分别从男与女2个数据集中随机选取了1万、5万、10万、20万、50万、100万、200万和全部的数据作为数据集分别测试，分别标记Mlw

35、，M5w，M10w，M20w，M50w，M100w，M200w，MTotal和Flw，FSw，FlOw，F20w，F50w，F100w，F200w，FTota下面将Naive算法(标记为NA)与改进算法(标记为PB，包括算法3和算法4)进行比较，2个算法均在相同的数据集上进行以保证算法的可比性实验主要目的是验证算法的正确性与算法的效率。算法正确性通过比较2个算法识别出来的实体结果来验证，算法效率通过比较算法的运行时间来验证本文的实验环境为IntelXeonCPU 24 GHz和RAM 8 GB，所有的算法和评估程序均采用C+实现万方数据782 计算机研究与发展2016，53(4)52 算法结果

36、表2和表3分别给出了实体识别后的实体数量，实验结果表明2个算法出来的结果是完全一致的从表2和表3可以看出，从1986年至今我国从事自然科学研究的学者共有2 862 749人，其中女性与男性分别有1 171 655和1 690 394位，包括了各种行业各个级别的自然科学研究者，比如教授、副教授、教授级高级工程师等高级职称研究者和博士生、研究生等各个层次Table 2 Number of Entities(Female)表2实体数量(女研究者)F1wF5WF10wF20wF50wF100wF200wTable 3 Number of Entities(Male)表3实体数量(男研究者)Data S

37、et NumberM1wM5wM10WM20wM50wM100WM200W8 7444000667 345120 997250 088390 347609 99453运行时间表4比较Naive算法(NA)与改进算法(PB)的运行时间从运行时间上看，NA算法的运行时间明显比PB算法要短，而且NA算法的运行时间特征明显：运行时间与数据集大小的平方成正比，比如当数据集大小为50万，运行时间是7 776 S左右，从而可以得出在100万数据集上的运行时间大概是7 776 S的4倍，与实际运行时间相处无几PB算法共需要进行3次数据集的划分，分别基于姓名、出生日期与证件号码进行划分后合并从时间上来看，2个算

38、法时问差别比较显著，尤其是当算法在女研究者数据全集上进行时NA算法执行112 h，如果在男研究者数据全集上运行预计需要300 h，因此不在男研究者全集中执行Naive算法Table 4 Running Time表4运行时间 s从PB算法来看，基于不同的属性划分会产生不同的计算代价，其主要原因跟属性值的分布密切相关，如果某个属性在某个值上的重复值较多，那么交叉验证时间比较多表5中PBl是算法3选择姓名、出生日期与证件号码进行了3次划分，而PB-2选择姓名、邮件和证件号码进行了3次划分，二者时间差别很大，这是由于Email属性值上重复值不多，而出生日期重复的情况比较多表6比较2个算法在男研究者数据

39、集上的运行时间，结果是完全类似的Table 5 Running Time of Different Attributes(Female)表5 不同的属性划分比较(女研究者) STable 6 Running Time of Different Attributes(Male)表6不同的属性划分比较(男研究者) s万方数据何贤芒等：基于项目合作的社会关系网络构建 783表7给出了PBl选择姓名、出生日期与证件号码作为分组的属性，而PB-2选择姓名、邮件和证件号码作为分组的属性，算法的主要时间是3次分组和2次合并(表7中分别记为PARl，PAR2，PAR3，MERl和MER2)从表7可以看出，算法

40、的主要运行时间在第2次分组上，而选择邮件作为分组的依据比选择出生日期节省较多的时间，这是由于邮件重复的情形比出生日期要少很多Table 7 Composition of Running Time表7运行时间的构成 S6 总 结如何从海量数据中发现基础研究人员的合作关系，对于科学基金项目的全过程管理，为科学基金项目管理提供辅助检索与查询，保证科学基金的公正与公平，具有重要的研究价值和现实需求针对历年累积的申请书中的合作关系，本文提出了基于项目合作关系的基础研究人员社会网络关系的构建从实验结果来看，1986-2014年我国从事自然科学研究的-【作者大概有280多万，其中男女比例大概是144：1针对

41、项目合作社会关系网络研究，我们将在社会网络结构分析、社会关系分析、社会影响分析与行为分析等方面开展工作，具体而言，包括基于项目合作网络的结构特征，从项目合作中挖掘出导师与学生关系、3人组(triad)形成等，这些工作的开展将会从另一视觉去审视基础研究人员的社会关系网络1234参 考 文 献Liu XGuo ZLin ZA local social network approach forresearch managementjDecision Support Systems，201 356(1 2)：427-438Tang J，Zhang JYao L。et al+ArnetMiner：Ext

42、raction andmining of academic social networkscProe of the 14thA(M SIGKDD Int Conf on Knowledge Discovery and DataMiningNew York：ACM，2008：990998China Computer FederationCCF ScholarEBOI，E201512-0e1http：ww,ccforbcnsitesccfccfschoIarjsp(inChinese)(计算机学会CCF学术空间EB()I。201512 02http：wwwccforgcnsitesccfccfsc

43、holarjsp)Cben WeiWang Zhongyuan，Yang Sen，et a1ScholarSpace：An academic space for computer science researchersJJournal of Computer Research and Development20 1 148(S3)395399 fin(1h】nese)5678910111 2131 415(陈威，E仲远杨森，等ScholarSpace：面向计算机领域的学术空间J计算机研究与发展201148(s3)：395 399)Erickson JOn the relative comple

44、xities of son3e geometricproblemsClOl。Proc of Canad Conf Computer Geometry20lo：8j 90L 2015 12-01http：IcsuiucedujeffepubspdfrelativepdfErickson JNew lower hounds for Hopcrofts problem EJDiscreteComputational Geometry，1 996，16(4)：389-418Gan Junhao，Tao YufeiDBSCAN revisited：MisClaimHnFixability，and app

45、roximationcProc of the 2015 ACMSIGM()f)Int Conf on Management of DataNew York：ACM，20l 5：5l 9-530Shi I。Fong H，Tang Jet a1VEGAS：Visual influencegraph summarization on citation networksJIEEE Transoil KnowledgeData Engineering，201 5，27(12)!l一1 5Ao WenJingStudy of mining social network based on callrecor

46、ds ED Guangzhou：South China University ofTechnology，2013(in Chinese)(敖文井，基于通话记录的社会关系网络挖掘D广州：华南理r大学，2013)Zhang JFang Z，Chen Wet a1Diffusion of“Following”links in microblogging networksJIEEE Trans onKnowledge&Data Engineering，2015，27(8)：20932106Tang J，Wang B。Yang Y，et a1PatentMiner：Topicdrivenpatent a

47、nalysis and miningcProc of the 18th ACMSIGKDD Int Conon Knowledge Discovery and Data MiningNew York：ACM，20 12：1366一1375Su n J，Tang JA Survey of Models and Algorithms forSocial Influence AnalysisMSocial Network DataAnalyticsBerlin：Springer20l 1：177214Kumar R Mahdian M， McGlohon MDynamics ofconversationscProc of the 16th ACM SIGKDD Int Confon Knowledge Discovery and Data MiningNew York：ACM，2010：553562Grum D，Guha R，Liben Nowell D，et a1Informationdiffusion through blogspacecProc of the 1 3th Int Confon World Wide WebNew York：ACM，2004：49卜50lMishra N，Schrei