社会网络中潜在重要节点发现关键技术研究

结题报告

项目介绍

AI项目解读

基本信息

批准号：
61170064
项目类别：
面上项目
资助金额：
59.0万
负责人：
王朝坤
依托单位：
清华大学
学科分类：
F0202.系统软件、数据库与工业软件
结题年份：
2015
批准年份：
2011
项目状态：
已结题
起止时间：
2012-01-01 至2015-12-31

项目参与者：
谌卫军；闻立杰；刘璋；余志伟；彭卓；韩璐；白易元；欧晓平；
关键词：
潜在重要节点发现天际线节点重要性度量社会网络潜在重要节点

项目摘要

近年来在线社交网络社区的普及使得社会网络的研究越来越受到关注，成员在社会网络中的作用和重要性也吸引着越来越多人的注意。然而该领域目前的研究成果远远不能满足现实中的应用需求。本项目旨在提出并研究社会网络中潜在重要节点发现问题。在整理分析节点重要性度量指标集合的基础上，建立基于天际线的社会网络潜在重要节点模型；通过多级倒排及Bitmap等索引结构，实现多指标的增量式快速计算；通过启发式规则有效减小候选潜在重要节点集合规模，依据组合递推方法按代价序生成给定节点的提升方案，支持加权社会网络潜在重要节点的快速发现；建立混合动力演化模型精确刻画社会网络的演化过程，同时基于MapReduce计算框架有效发现大规模动态社会网络中的潜在重要节点。社会网络中潜在重要节点发现问题具有重要的理论研究意义和实际应用价值,本项目的研究成果可望广泛应用于新星发现、商业遴选、传染病防治，以及反恐维稳等关键国家安全领域。

结项摘要

本项目旨在提出并研究社会网络中潜在重要节点发现问题。经过4年的研究工作，课题组发表学术论文34篇，其中SCI论文6篇、EI论文15篇，CCF A类长文7篇，申请国家发明专利5项，获得国内外最佳会议论文奖3项。.在整理分析节点重要性度量指标集合的基础上，建立基于天际线的社会网络潜在重要节点模型；针对不等边权社会网络，提出了“暴力法”、“基于索引的动态剪枝法”两个基准算法，之后提出了 “提升边界”、“方案下界”等概念用于对提升方案空间进行有效剪枝，并根据排列组合定理提出了按方案成本升序对方案进行依次检验的策略，进而提出了“基于提升边界的组合递推提升法”的优化算法。该成果发表于WWWJ。针对等边权社会网络，首先基于“提升边界”提出了直接计算成员提升成本的方法，然后基于“次天际线”等概念对候选成员空间进行了显著有效的剪枝，进而提出了“基于次天际线与提升边界的提升法”的优化算法，成果获得APWEB 2012最佳论文奖。.从用户行为驱动的角度，建立混合动力演化模型精确刻画社会网络的演化过程。针对社交链接产生方向推断问题，从真实数据中总结了四个一般性的交友行为方向模式，提出了以降低模式背离度为目标的ReDirect优化框架，以及基于ReDirect的链接方向推断算法。该成果发表于WWW；针对社会网络演化过程推断问题，提出了用以表达社会网络演化过程的潜在朋友关系传递树LaFT-Tree，设计了交友行为生成模型LaFT-LDA，以及基于LaFT-LDA模型级联推断的LaFT-Tree推断算法。LaFT-Tree将扁平的网络结构层次化，直观展示了用户以其现有朋友为中介人扩张其社会网络的过程。该成果发表于WSDM和KDD；针对社会网络链接预测问题，提出了基于传递性原理的、用户兴趣感知的交友行为生成模型LFPM，在此基础上构造了用以刻画潜在朋友关系传播轨迹和趋势的LFPN，进而将用户的交友行为看作是在用户自身兴趣和来自朋友的联合影响作用下的结果，提出了基于LFPN的社交链接预测算法LFPN-RW。该成果发表于SIGIR；提出了连续时域上的基于个人偏好和社交影响联合作用的用户时效行为生成模型ConTyor，利用动态偏好空间DP-Space来刻画各个影响因子的动态变化，提出了用于模型推断的EMO算法，展示了ConTyor作为一个通用的行为生成模型在多个真实场景中的应用。成果发表于PVLDB。