一种基于最大公共子图的社交网络对齐方法
作者:
作者单位:

作者简介:

冯朔(1989-),男,辽宁沈阳人,学士,CCF学生会员,主要研究领域为社交网络用户识别,网络对齐;寇月(1980-),女,博士,副教授,CCF专业会员,主要研究领域为实体搜索,数据挖掘;申德荣(1964-),女,博士,教授,博士生导师,CCF高级会员,主要研究领域为分布式数据管理,数据集成;于戈(1962-),男,博士,教授,博士生导师,CCF会士,主要研究领域为数据库,大数据管理;聂铁铮(1980-),男,博士,副教授,CCF专业会员,主要研究领域为数据质量,数据集成.

通讯作者:

冯朔,E-mail:fengshuo1989818@hotmail.com

中图分类号:

TP311

基金项目:

国家重点基础研究发展计划(973)(2012CB316201);国家自然科学基金(U1435216,61672142,61472070,61602103);国家重点研发计划(2018YFB1003404)


Maximum Common Subgraph Based Social Network Alignment Method
Author:
Affiliation:

Fund Project:

National Basic Research Program of China (973) (2012CB316201); National Natural Science Foundation of China (U1435216, 61672142, 61472070, 61602103); National Key R&D Program of China (2018YFB1003404)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    随着Internet的普及,各类社交网络走进人们的视野,用户为满足不同的服务需求,往往不会局限于单一社交网络中,因此,跨社交网络环境下的用户识别问题成为研究者的热门话题.主要利用网络结构信息,针对社交网络对齐问题进行研究,主要包含以下研究点:首先,将网络对齐问题抽象为最大公共子图问题(α-MCS),并提出求解自适应参数α的方法,相比于传统的基于启发式定义参数α的方法,该方法可有效区分不同类型网络中匹配用户与非匹配用户;其次,为快速而准确地解决α-MCS,提出了基于最大公共子图的迭代式网络对齐算法MCS_INA(α-MCS based iterative network alignment algorithm),该算法每次迭代过程主要包含两个阶段.第1个阶段,分别在两个社交网络中选取各自的候选匹配用户,第2个阶段,针对候选匹配用户进行识别.相比于其他算法,MCS_INA时间代价低,且依据不同网络特征,通过参数估计,可保证较高的识别精度;最后,在真实数据集和合成数据集中验证了算法MCS_INA的有效性.

    Abstract:

    With the popularization of Internet, plenty of social networks come into lives. To enjoy different services, users usually take part in multiple social networks simultaneously. Therefore, user identification across social networks has become a hot research topic. In this study, social network structure is used to solve the problem of network alignment. Firstly, the problem of network alignment is formalized as the problem of maximum common subgraph (α-MCS). A method is proposed to determine parameter α adaptively. Compared with the other heuristic methods on determiningα, the proposed method can distinguish matched users and unmatched users effectively on different kinds of social networks. Secondly, in order to fast answer α-MCS, algorithm MCS_INA (α-MCS based iterative network alignment algorithm) is proposed. MCS_INA mainly contains two steps in each iteration. In the first step, MCS_INA aims at selecting candidates in the two networks respectively. In the second step, a mapping algorithm is proposed to match candidates. Compared with other methods, MCS_INA has lower time complexity and higher identification accuracy on different networks. At last, experiments are conducted on real-world and synthetic datasets to demonstrate the effectiveness of the proposed algorithm MCS_INA.

    参考文献
    相似文献
    引证文献
引用本文

冯朔,申德荣,聂铁铮,寇月,于戈.一种基于最大公共子图的社交网络对齐方法.软件学报,2019,30(7):2175-2187

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2018-07-20
  • 最后修改日期:2018-11-22
  • 录用日期:
  • 在线发布日期: 2019-07-04
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号