| 摘要: |
| 随着Internet的普及，各类社交网络走进人们的视野，用户为满足不同的服务需求，往往不会局限于单一社交网络中，因此，跨社交网络环境下的用户识别问题成为研究者的热门话题.主要利用网络结构信息，针对社交网络对齐问题进行研究，主要包含以下研究点：首先，将网络对齐问题抽象为最大公共子图问题（α-MCS），并提出求解自适应参数α的方法，相比于传统的基于启发式定义参数α的方法，该方法可有效区分不同类型网络中匹配用户与非匹配用户；其次，为快速而准确地解决α-MCS，提出了基于最大公共子图的迭代式网络对齐算法MCS_INA（α-MCS based iterative network alignment algorithm），该算法每次迭代过程主要包含两个阶段.第1个阶段，分别在两个社交网络中选取各自的候选匹配用户，第2个阶段，针对候选匹配用户进行识别.相比于其他算法，MCS_INA时间代价低，且依据不同网络特征，通过参数估计，可保证较高的识别精度；最后，在真实数据集和合成数据集中验证了算法MCS_INA的有效性. |
| 关键词: 社交网络 最大公共子图 用户识别 网络对齐 |
| DOI：10.13328/j.cnki.jos.005831 |
| 分类号:TP311 |
| 基金项目:国家重点基础研究发展计划（973）（2012CB316201）；国家自然科学基金（U1435216，61672142，61472070，61602103）；国家重点研发计划（2018YFB1003404） |
|
| Maximum Common Subgraph Based Social Network Alignment Method |
|
FENG Shuo, SHEN De-Rong, NIE Tie-Zheng, KOU Yue, YU Ge
|
|
School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
|
| 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. |
| Key words: social network maximum common subgraph user identification network alignment |
