《弱社会关系的团队形成问题研究Researchonteamformationofweaksocialrelations.ppt》由会员分享，可在线阅读，更多相关《弱社会关系的团队形成问题研究Researchonteamformationofweaksocialrelations.ppt（18页珍藏版）》请在三一文库上搜索。
1、,社交网络中的弱关系团队形成问题研究,1,18,孙焕良 富珊珊 刘俊岭 于戈 许鸿斐,沈阳建筑大学 信息与控制工程学院 辽宁沈阳 东北大学 信息科学与工程学院 辽宁沈阳,2,研究背景 问题定义 弱关系团队查询算法 实验结果与分析,目录：,18,一、研究背景,3,18,传统团队形成问题,1.1 团队形成问题,不考虑人与人之间的社会关系,满足任务需求,基于社会网络的团队形成问题,满足任务需求,将成员间社会关系作为团队优劣的衡量标准,社会网络中的团队形成问题,共同特点：团队成员间需紧密联系。,存在另一类团队成员间联系“不紧密”需求：如项目评审、广告投放。,4,弱关系优点：传播效率高；弱关系团队的观点
2、具有多样化、多角度、无偏见等特点。,18,2.1 问题描述,二、问题定义,P=(a1, 2), (a2, 1), (a3, 2),设结点间跳数大于 1 时为弱关系,T1=v1, v2, v5, v7, v9,38,T2=v1, v3, v5, v7, v9,42,5,18,社会网络中的弱关系团队形成问题,一个团队,评价标准：团队总分值越高越好,关键字约束,弱关系约束,6,18,两个约束,NP-Hard问题,如何快速、高效的搜索到社会网络中高质量的弱关系团队？,2.2 问题定义,三、弱关系团队查询算法,7,18,3.1 贪心算法,基于结点分值的贪心策略,从关键字索引中分值最大的结点向后搜索,基于
3、结点分值与图结构的贪心策略,关键字分值,结点度,8,18,时间复杂度O(N2),3.2 精确算法,回溯搜索算法,9,18,10,两个剪枝策略：,利用弱关系和关键字约束剪去不满足约束的子树,(2)利最优解团队中每个元素下界位置进行剪枝,虽然利用剪枝条件缩减了搜索空间，但是解空间内仍需对大量结点替换，导致运行效率降低。,18,3.2 精确算法,动态规划搜索算法,如不考虑弱关系约束,可采用动态规划求解,问题转换为01背包问题,如考虑弱关系约束,不满足最优子结构性质,考虑保留多个满足弱关系的候选解,18,两个剪枝策略：,（2）提前结束遍历候选集,（1）对不可能为最优解的中间解进行剪枝,11,3.3 -
4、近似算法,在动态规划算法基础上实现,基本思想：为每个子问题设置边界值，边界值优于各子问题的最优解，加入解空间内的解需满足边界值的近似率。,18,12,四、实验结果与分析,4.1 数据集 ACM数据集 连通无权图，20000个结点，80002条边。弱关系采用跳数度量。 DBLP数据集 连通带权图，6333个结点，26420条边。弱关系采用最短路径边权和度量。,13,18,算法运行效率 查询结果质量,团队影响结点数,团队结点所占社区数,团队影响力,4.2 评价方法,4.2.1 算法效率分析,精确算法运行效率比较,14,18,近似算法运行效率,4.2.2 查询结果质量分析,15,Greedy基于结点分值贪心策略,ApproxDP近似算法,18,4.2.3 团队影响力分析,16,采用独立级联模型进行团队影响力分析。,TeamMD为使用MD算法所求团队。,TeamSCG为使用SCG算法所求团队。,TeamMW不考虑弱关系，取前K大经验值的结点生成团队。,18,团队影响结点数比较,TeamADP为近似算法所求团队。,弱关系团队,非弱关系团队,17,采用fast unfolding算法对数据集进行社区划分。,将ACM数据集划分为54个社区。,将DBLP数据集划分为27个社区。,18,团队结点所占社区数比较,18,THE END,THANK YOU!,18,