弱社会关系的团队形成问题研究Researchonteamationofweaksocialreltions

1、社交网络中的弱关系团队形成问社交网络中的弱关系团队形成问题研究题研究118孙焕良 富珊珊 刘俊岭 于戈 许鸿斐沈阳建筑大学 信息与控制工程学院 辽宁沈阳东北大学 信息科学与工程学院 辽宁沈阳2 研究背景 问题定义 弱关系团队查询算法 实验结果与分析目录：18一、研究背景一、研究背景318传统团队形成问题1.1 团队形成问题团队形成问题不考虑人与人之间的社会关系满足任务需求基于社会网络的团队形成问题满足任务需求将成员间社会关系作为团队优劣的衡量标准社会网络中的团队形成问题共同特点：团队成员间需紧密联系。 存在另一类团队成员间联系“不紧密”需求：如项目评审、广告投放。4 弱关系优点：传播效率高；弱

2、关系团队的观点具有多样化、多角度、无偏见等特点。182.1 问题描述问题描述二、问题定义二、问题定义p=(a1, 2), (a2, 1), (a3, 2)设结点间跳数大于设结点间跳数大于 1 时为弱关系时为弱关系t1=v1, v2, v5, v7, v938t2=v1, v3, v5, v7, v942518社会网络中的弱关系团队形成问题 一个团队评价标准：团队总分值越高越好关键字约束弱关系约束618 两个约束np-hard问题如何快速、高效的搜索到社会网络中高质量的弱关系团队？2.2 问题定义问题定义三、弱关系团队查询算法三、弱关系团队查询算法7183.1 贪心算法基于结点分值的贪心策略基于

3、结点分值的贪心策略从关键字索引中分值最大的结点向后搜索基于结点分值与图结构的贪心策略基于结点分值与图结构的贪心策略关键字分值结点度818时间复杂度o(n2)3.2 精确算法回溯搜索算法回溯搜索算法91810 两个剪枝策略：(1)利用弱关系和关键字约束剪去不满足约束的子树(2)利最优解团队中每个元素下界位置进行剪枝虽然利用剪枝条件缩减了搜索空间，但是解空间内仍需对大量结点替换，导致运行效率降低。183.2 精确算法动态规划搜索算法动态规划搜索算法如不考虑弱关系约束 可采用动态规划求解问题转换为01背包问题如考虑弱关系约束 不满足最优子结构性质 考虑保留多个满足弱关系的候选解18两个剪枝策略：（2

4、）提前结束遍历候选集（1）对不可能为最优解的中间解进行剪枝113.3 -近似算法 在动态规划算法基础上实现 基本思想：为每个子问题设置边界值，边界值优于各子问题的最优解，加入解空间内的解需满足边界值的近似率。1812四、实验结果与分析四、实验结果与分析4.1 数据集acm数据集 连通无权图，20000个结点，80002条边。弱关系采用跳数度量。dblp数据集 连通带权图，6333个结点，26420条边。弱关系采用最短路径边权和度量。1318算法运行效率查询结果质量 团队影响结点数团队结点所占社区数 团队影响力4.2 评价方法 4.2.1 算法效率分析算法效率分析精确算法运行效率比较1418近似算法运行效率4.2.2 查询结果质量分析查询结果质量分析15greedy基于结点分值贪心策略approxdp近似算法184.2.3 团队影响力分析团队影响力分析16采用独立级联模型进行团队影响力分析。teammd为使用md算法所求团队。teamscg为使用scg算法所求团队。teammw不考虑弱关系，取前k大经验值的结点生成团队。18团队影响结点数比较teamadp为近似算法所求团队。弱关系团队非弱关系团队17采用fast unfolding算法对数据