当前位置:主页 > 科技论文 > 软件论文 >

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

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

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

【文章页数】:88 页

【学位级别】:硕士

【部分图文】:

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


图4.1社交网络图模型的最小度的影响??

幂律指数,最小度,满意度


宄改变最小度的值对我们的实验结果的影响。我们设定用户数(即节点数)为??500,事件数为50,幂律指数为1.5,最小度dwi?依次为1,5,10,100和200。??从图4.1(a)中我们可以看出边的数量随着最小度的增大而增加,其原因是显而易??见的,当最小度增大时,图的稠密程度无疑会增加。在我们接下来的实验中,我??们设置=?10表不稀疏图,=?1〇〇表不稠密图。我们用Base表不基准??算法,用Greedy表示满意度增益启发式算法,用LAG表示前向检验优化启发式??算法。???10*???*???????????L3?280??p|?I?^??1??6?//?*??H??,?r?m?I??E,?/?^?l"??/?ln?i??/?100?'?I??,/?。』L?EL」EL?0..?Q-?50?j?:?!?j?J??0?1?6?10?100?aoo?1?6?10?100?J00??0?30?40??0?80?100?130?140?>40?180?aoo??????|BBBM?8s〇wdyECLAQ?|?|aBB-tB5QwriyL[iIAO?|??(a)边-最小度?(b)总满意度-最小度?(c)后悔率-最小度??图4.1社交网络图模型的最小度的影响??如图4.1(b)所示,随着最小度的增大,安排的总体满意度成比例增加。而我??们的Greedy和LAG算法明显比Base更优。从图4.1(c)中可以看出

网络图,幂律指数,社交,满意度


Greedy(s)?1.95?2.13?2.54?2.6?3.22??LAG(s)?1.53?1.57?1.08?1.58?1.43??安排总体满意度.从图4.2(a)中,我们可以观察到在稀疏图中随着幂律指数??从1增加到3.5,由于社交网络图G?=?([/,扔变得愈发稀疏,所以安排的总体满??意度持续下降。特别的是,当幂律指数大于2.5时,Greedy和LAG两个算法得??到的结果几乎没有差别。所以,在之后的实验中为了更好得比较两个算法的差??另IJ,我们将幂律指数设置为1.5。而在图4.3(a)中,可以看到在稠密图中安排的??总体满意度随着幂律指数的变化没有那么明显。??后悔率.从图4.2(b)中,我们可以发现在稀疏图中,LAG算法的后悔率比??Greedy算法的后悔率低了?5%到8%左右。而且随着社交网络图愈发稀疏,其差??距愈发明显。不过在稠密图中,我们发现两个算法的后悔率大小差异不大。??运行时间.从表4.3和表4.4中


本文编号:3471043

资料下载
论文发表

本文链接:https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3471043.html


Copyright(c)文论论文网All Rights Reserved | 网站地图 |

版权申明:资料由用户a4019***提供,本站仅收录摘要或目录,作者需要删除请E-mail邮箱bigeng88@qq.com