基于社交网络的团队与事件组织算法研究

发布时间：2021-11-02 01:09

　　团队与事件组织问题是经典的组合优化问题,在运筹学领域早已进行了广泛的研究。但是,随着网络通信的高速发展以及各种社交平台的流行,社交网络背景下的团队与事件组织问题再次引起了众多研究人员的注意。由于与社交网络的结合,使得社交网络中的团队与事件组织问题与传统版本的问题不同,从而其不能再简单地借助针对集合覆盖或背包问题等经典问题的近似算法来解决。因此,在充分调研、结合现实情景的基础上,我们首次正式定义了基于社交网络的团队组织收益通信比最大化问题、基于社交网络的事件组织满意度最大化问题和基于社交网络的旅行规划效用最大化问题。随后,我们证明了这三个问题都是NP难问题,并且基于社交网络的团队组织收益通信比最大化问题和基于社交网络的事件组织满意度最大化问题不存在多项式时间近似方案。为了解决基于社交网络的团队组织收益通信比最大化问题,我们设计了专家启发式和项目启发式两个算法;关于基于社交网络的事件组织满意度最大化问题,我们设计了满意度增益启发式算法和前向检验优化启发式算法;针对基于社交网络的旅行规划效用最大化问题,我们则设计了效用启发式算法和相似度启发式算法。最后,我们在仿真和真实数据集上进行了大量的实... 

【文章来源】：中国科学技术大学安徽省 211工程院校 985工程院校

【文章页数】：88 页

【学位级别】：硕士

【部分图文】：

图４．１社交网络图模型的最小度的影响??

宄改变最小度的值对我们的实验结果的影响。我们设定用户数（即节点数）为??５００，事件数为５０，幂律指数为１．５，最小度ｄｗｉ？依次为１，５，１０，１００和２００。??从图４．１（ａ）中我们可以看出边的数量随着最小度的增大而增加，其原因是显而易??见的，当最小度增大时，图的稠密程度无疑会增加。在我们接下来的实验中，我??们设置＝?１０表不稀疏图，＝?１〇〇表不稠密图。我们用Ｂａｓｅ表不基准??算法，用Ｇｒｅｅｄｙ表示满意度增益启发式算法，用ＬＡＧ表示前向检验优化启发式??算法。??？１０＊?？？＊???????????Ｌ３?２８０??ｐ｜?Ｉ?＾??１??６?／／?＊？?Ｈ??，?ｒ?ｍ?Ｉ??Ｅ，?／?＾?ｌ＂??／?ｌｎ?ｉ??／?１００?＇?Ｉ??，／?。』Ｌ?ＥＬ」ＥＬ?０．．?Ｑ－?５０?ｊ?：?！?ｊ?Ｊ??０?１?６?１０?１００?ａｏｏ?１?６?１０?１００?Ｊ００??０?３０?４０?？０?８０?１００?１３０?１４０?＞４０?１８０?ａｏｏ??????｜ＢＢＢＭ？８ｓ〇ｗｄｙＥＣＬＡＱ?｜?｜ａＢＢ－ｔＢ５ＱｗｒｉｙＬ［ｉＩＡＯ?｜??（ａ）边－最小度?（ｂ）总满意度－最小度?（ｃ）后悔率－最小度??图４．１社交网络图模型的最小度的影响??如图４．１（ｂ）所示，随着最小度的增大，安排的总体满意度成比例增加。而我??们的Ｇｒｅｅｄｙ和ＬＡＧ算法明显比Ｂａｓｅ更优。从图４．１（ｃ）中可以看出

Ｇｒｅｅｄｙ（ｓ）?１．９５?２．１３?２．５４?２．６?３．２２??ＬＡＧ（ｓ）?１．５３?１．５７?１．０８?１．５８?１．４３??安排总体满意度．从图４．２（ａ）中，我们可以观察到在稀疏图中随着幂律指数??从１增加到３．５，由于社交网络图Ｇ?＝?（［／，扔变得愈发稀疏，所以安排的总体满??意度持续下降。特别的是，当幂律指数大于２．５时，Ｇｒｅｅｄｙ和ＬＡＧ两个算法得??到的结果几乎没有差别。所以，在之后的实验中为了更好得比较两个算法的差??另ＩＪ，我们将幂律指数设置为１．５。而在图４．３（ａ）中，可以看到在稠密图中安排的??总体满意度随着幂律指数的变化没有那么明显。??后悔率．从图４．２（ｂ）中，我们可以发现在稀疏图中，ＬＡＧ算法的后悔率比??Ｇｒｅｅｄｙ算法的后悔率低了?５％到８％左右。而且随着社交网络图愈发稀疏，其差??距愈发明显。不过在稠密图中，我们发现两个算法的后悔率大小差异不大。??运行时间．从表４．３和表４．４中


本文编号：3471043