融合社区检测的协作众包任务分配方法

doi:10.11772/j.issn.1001-9081.2024030274

《计算机应用》唯一官方网站 ›› 2025, Vol. 45 ›› Issue (2): 534-545.DOI: 10.11772/j.issn.1001-9081.2024030274

• 先进计算 • 上一篇

融合社区检测的协作众包任务分配方法

胡林波¹^,², 倪志伟¹^,²(), 程家乐¹^,², 刘文涛¹^,², 朱旭辉¹^,³

^1.合肥工业大学管理学院，合肥 230009
^2.过程优化与智能决策教育部重点实验室（合肥工业大学），合肥 230009
^3.智能互联系统安徽省实验室（合肥工业大学），合肥 230009

收稿日期:2024-03-15 修回日期:2024-04-16 接受日期:2024-04-19 发布日期:2024-05-21 出版日期:2025-02-10
通讯作者: 倪志伟
作者简介:胡林波（1997—），男，江西吉安人，硕士研究生，主要研究方向：智能计算、空间众包
程家乐（2000—），男，安徽淮南人，硕士研究生，主要研究方向：深度学习、路径规划
刘文涛（1997—），男，安徽合肥人，博士研究生，主要研究方向：深度学习、智能计算
朱旭辉（1991—），男，安徽阜阳人，讲师，博士，主要研究方向：深度学习、智能计算。
基金资助:
国家自然科学基金资助项目(72171073);安徽省科技重大专项(201903a05020020)

Collaborative crowdsourcing task allocation method fusing community detection

Linbo HU¹^,², Zhiwei NI¹^,²(), Jiale CHENG¹^,², Wentao LIU¹^,², Xuhui ZHU¹^,³

^1.School of Management，Hefei University of Technology，Hefei Anhui 230009，China
^2.Key Laboratory of Process Optimization and Intelligent Decision-making，Ministry of Education（Hefei University of Technology），Hefei Anhui 230009，China
^3.Intelligent Interconnected System Anhui Provincial Laboratory （Hefei University of Technology），Hefei Anhui 230009，China

Received:2024-03-15 Revised:2024-04-16 Accepted:2024-04-19 Online:2024-05-21 Published:2025-02-10
Contact: Zhiwei NI
About author:HU Linbo， born in 1997， M. S. candidate. His research interests include intelligent computing， spatial crowdsourcing.
CHENG Jiale， born in 2000， M. S. candidate. His research interests include deep learning， path planning.
LIU Wentao， born in 1997， Ph. D. candidate. His research interests include deep learning， intelligent computing.
ZHU Xuhui， born in 1991， Ph. D.， lecturer. His research interests include deep learning， intelligent computing.
Supported by:
National Natural Science Foundation of China(72171073);Science and Technology Major Special Project of Anhui Province(201903a05020020)

摘要/Abstract

摘要：

针对传统协作众包任务分配中忽视工人协作关联的问题，将工人之间的社交及历史合作关系纳入考虑范畴，提出一种融合社区检测的协作众包任务分配方法。首先，利用社区检测算法挖掘众包工人之间潜在的社交关系，形成候选社群；其次，定义协作度、交互成本和众包任务分配效用等要素后，构建综合考虑技能覆盖率、信誉度及预算成本的协作众包任务分配模型；再次，引入Piece-Wise混沌映射、柯西分布逆累积函数算子、自适应正切飞行算子和麻雀警戒机制等策略，并提出改进沙猫群优化（SCSO）算法——TSCSO；最后，利用TSCSO算法对前述模型进行求解。在不同规模真实数据集合成的算例上的实验结果表明，所提算法可使任务分配成功率维持在90%及以上水平，相较于其他改进智能算法任务分配效用平均提升20.08%~53.38%，验证了所提算法在协作众包任务分配问题中的适用性、稳定性和有效性。

关键词: 协作众包, 社区检测, 协作候选社群, 任务分配, 沙猫群优化算法

Abstract:

To address the issue of neglecting workers’ collaborative relationships in traditional collaborative crowdsourcing task allocation， a collaborative crowdsourcing task allocation method fusing community detection was proposed， by considering the social and historical cooperative relationships among workers. Firstly， potential social relationships among crowdsourced workers were mined by a community detection algorithm to establish candidate communities. Secondly， after defining factors such as degree of collaboration， interaction cost， and utility of task allocation， a model for collaborative crowdsourcing task allocation was developed by considering skill coverage， credibility， and budget comprehensively. Thirdly， the strategies such as Piece-Wise chaotic mapping， inverse cumulative function operator based on Cauchy distribution， adaptive tangent flight operator， and sparrow warning mechanism were introduced and an optimized Sand Cat Swarm Optimization （SCSO） algorithm — TSCSO was proposed. Finally， TSCSO algorithm was used to solve the aforementioned model. Experimental results on examples synthesized from real datasets of different scales demonstrate that the proposed algorithm has the task allocation success rate of at least 90%. Furthermore， TSCSO algorithm improves the average task allocation utility ranging by 20.08% to 53.38% compared to other optimized intelligent algorithms， verifying the proposed algorithm’s applicability， stability， and efficacy in collaborative crowdsourcing task allocation problems.

Key words: collaborative crowdsourcing, community detection, collaborative candidate community, task allocation, Sand Cat Swarm Optimization (SCSO) algorithm

中图分类号:

TP301.6

胡林波, 倪志伟, 程家乐, 刘文涛, 朱旭辉. 融合社区检测的协作众包任务分配方法[J]. 计算机应用, 2025, 45(2): 534-545.

Linbo HU, Zhiwei NI, Jiale CHENG, Wentao LIU, Xuhui ZHU. Collaborative crowdsourcing task allocation method fusing community detection[J]. Journal of Computer Applications, 2025, 45(2): 534-545.

图/表 12

图1 融合社区检测的复杂协作众包任务分配框架

Fig. 1 Complex collaborative crowdsourcing task allocation framework fusing community detection

图2 利用PWLCM机制进行沙猫种群初始化生成的散点图和频率分布直方图

Fig. 2 Scatter map and frequency distribution histogram generated by using PWLCM mechanism for initialization of sand cat population

图3 采用柯西分布逆累积函数算子策略改进的沙猫游走轨迹

Fig. 3 Sand cat wandering trajectory improved by Cauchy distribution-based inverse cumulative function operator strategy

图4 采用自适应正切飞行算子策略改进的沙猫游走轨迹

Fig. 4 Sand cat wandering trajectory improved by adaptive tangent flight operator strategy

图5 CCC-WCM-TSCSO方案整体流程

Fig. 5 Overall process of CCC-WCM-TSCSO scheme

表1 算例的具体信息

Tab. 1 Details of examples

真实数据映射（包含与工人数和

协作权重相对应的节点和边）

表2 实验算法的参数设置

Tab. 2 Parameter setting of experimental algorithms

算法	相关参数	取值
TSCSO	$S M, r ⃗ G, R ⃗$	$S M = 2$ ， $r ⃗ G ∈ [2,0]$ ， $R ⃗ ∈ [- 2 r ⃗ G, 2 r ⃗ G]$
CCC-WCM- TSCSO	$α, β, γ$	$α = 0.6$ ， $β = 0.3$ ， $γ = 0.1$
	$s i, r i, q i$	$s i ∈ [0.5,0.9]$ ， $r i ∈ [100,300]$ ， $q i ∈ [0.5,0.9]$
	$u h i, b h i, k k i$	$u h i ∈ [0.5,0.9]$ ， $b h i$ 和 $k h i$ 的取值根据不同数据集大小设置相应的范围

表2 实验算法的参数设置

Tab. 2 Parameter setting of experimental algorithms

算法	相关参数	取值
TSCSO	$S M, r ⃗ G, R ⃗$	$S M = 2$ ， $r ⃗ G ∈ [2,0]$ ， $R ⃗ ∈ [- 2 r ⃗ G, 2 r ⃗ G]$
CCC-WCM- TSCSO	$α, β, γ$	$α = 0.6$ ， $β = 0.3$ ， $γ = 0.1$
	$s i, r i, q i$	$s i ∈ [0.5,0.9]$ ， $r i ∈ [100,300]$ ， $q i ∈ [0.5,0.9]$
	$u h i, b h i, k k i$	$u h i ∈ [0.5,0.9]$ ， $b h i$ 和 $k h i$ 的取值根据不同数据集大小设置相应的范围

表3 五种算法所求的众包任务分配效用值对比

Tab. 3 Comparison of utility values of crowdsourcing task allocation obtained by five algorithms

实验算例	指标	TSCSO	MSCSO^［38］	IGSO^［36］	Greedy^［37］	CTHHO^［32］
CF	最优值	1 676.58	1 627.29	1 676.06	1 469.10	1 676.81
	最劣值	1 628.33	1 382.94	1 537.99	763.16	1 452.13
	平均值	1 651.31	1 519.91	1 617.76	1 112.88	1 611.88
UAL	最优值	5 454.69	4 206.68	4 552.66	3 767.78	4 185.13
	最劣值	4 951.12	3 635.36	4 300.54	2 743.89	2 960.15
	平均值	5 188.83	3 808.00	4 438.86	3 334.35	3 539.10
FFN	最优值	22 367.68	14 141.23	15 731.54	14 382.18	12 452.55
	最劣值	19 717.50	10 227.78	14 218.23	12 899.28	11 600.87
	平均值	20 810.26	12 598.94	14 730.96	13 416.23	11 972.97

图6 不同规模数据集上5种算法的求解迭代曲线

Fig. 6 Solution iterative curves of five algorithms on datasets of different scales

图7 3个实验算例上5种算法所求Rtsa的柱状图对比

Fig. 7 Histogram comparison of Rtsa obtained by five algorithms on three experimental examples

图8 5种算法在UAL数据集上迭代1 000次的迭代曲线

Fig. 8 Iteration curves of five algorithms with 1 000 iterations on UAL dataset

图9 不同敏感参数对TSCSO算法性能的影响

Fig. 9 Influence of different sensitive parameters on TSCSO algorithm performance

参考文献 38

1	YANG C C， YEN J， LIU J. Social intelligence and technology［J］. IEEE Intelligent Systems， 2014， 29（2）： 5-8.
2	RAHMAN H， ROY S B， THIRUMURUGANATHAN S， et al. Task assignment optimization in collaborative crowdsourcing［C］// Proceedings of the 2015 IEEE International Conference on Data Mining. Piscataway： IEEE， 2015： 949-954.
3	GUO B， WANG Z， YU Z， et al. Mobile crowd sensing and computing： the review of an emerging human-powered sensing paradigm［J］. ACM Computing Surveys， 2016， 48（1）： No.7.
4	GUO B， LIU Y， WANG L， et al. Task allocation in spatial crowdsourcing： current state and future directions［J］. IEEE Internet of Things Journal， 2018， 5（3）： 1749-1764.
5	LIU Q， LUO T， TANG R， et al. An efficient and truthful pricing mechanism for team formation in crowdsourcing markets［C］// Proceedings of the 2015 IEEE International Conference on Communications. Piscataway： IEEE， 2015： 567-572.
6	HAMROUNI A， GHAZZAI H， ALELYANI T， et al. Low-complexity recruitment for collaborative mobile crowdsourcing using graph neural networks［J］. IEEE Internet of Things Journal， 2022， 9（1）： 813-829.
7	WANG L， YANG D， YU Z， et al. Acceptance-aware mobile crowdsourcing worker recruitment in social networks［J］. IEEE Transactions on Mobile Computing， 2022， 22（2）：634-646.
8	FU D， LIU Y. Trust-aware task allocation in collaborative crowdsourcing model［J］. The Computer Journal， 2021， 64（6）： 929-940.
9	YU D， ZHOU Z， WANG Y. Crowdsourcing software task assignment method for collaborative development［J］. IEEE Access， 2019， 7： 35743-35754.
10	ZHAO L， TAN W， LI B， et al. Multiple cooperative task assignment on reliability-oriented social crowdsourcing［J］. IEEE Transactions on Services Computing， 2022， 15（6）： 3402-3416.
11	BASIK F， GEDIK B， FERHATOSMANOĞLU H， et al. Fair task allocation in crowdsourced delivery［J］. IEEE Transactions on Services Computing， 2021， 14（4）： 1040-1053.
12	CHENG P， CHEN L， YE J. Cooperation-aware task assignment in spatial crowdsourcing［C］// Proceedings of the IEEE 35th International Conference on Data Engineering. Piscataway： IEEE， 2019： 1442-1453.
13	ZHOU J， ZENG A， FAN Y， et al. Identifying important scholars via directed scientific collaboration networks［J］. Scientometrics， 2018， 114（3）： 1327-1343.
14	JIANG J， AN B， JIANG Y， et al. Group-oriented task allocation for crowdsourcing in social networks［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2021， 51（7）： 4417-4432.
15	WANG W， HE Z， SHI P， et al. Strategic social team crowdsourcing： Forming a team of truthful workers for crowdsourcing in social networks［J］. IEEE Transactions on Mobile Computing， 2019， 18（6）： 1419-1432.
16	SHI Q， HAO D. Social sourcing： incorporating social networks into crowdsourcing contest design［J］. IEEE/ACM Transactions on Networking， 2023， 31（4）： 1535-1549.
17	JIANG J， AN B， JIANG Y， et al. Context-aware reliable crowdsourcing in social networks［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2020， 50（2）： 617-632.
18	WANG W， JIANG J， AN B， et al. Toward efficient team formation for crowdsourcing in noncooperative social networks［J］. IEEE Transactions on Cybernetics， 2017， 47（12）： 4208-4222.
19	BHATTI S S， FAN J， WANG K， et al. An approximation algorithm for bounded task assignment problem in spatial crowdsourcing［J］. IEEE Transactions on Mobile Computing， 2021， 20（8）： 2536-2549.
20	LIU Z， LI K， ZHOU X， et al. Multi-stage complex task assignment in spatial crowdsourcing［J］. Information Sciences， 2022， 586： 119-139.
21	ZHAO Y， ZHENG K， LI Y， et al. Destination-aware task assignment in spatial crowdsourcing： a worker decomposition approach［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 32（12）： 2336-2350.
22	CHENG P， LIAN X， CHEN L， et al. Task assignment on multi-skill oriented spatial crowdsourcing［J］. IEEE Transactions on Knowledge and Data Engineering， 2016， 28（8）： 2201-2215.
23	AZIZI M， AICKELIN U， KHORSHIDI H A， et al. Energy valley optimizer： a novel metaheuristic algorithm for global and engineering optimization［J］. Scientific Reports， 2023， 13： No.226.
24	HEIDARI A A， MIRJALILI S， FARIS H， et al. Harris hawks optimization： algorithm and applications［J］. Future Generation Computer Systems， 2019， 97： 849-872.
25	XUE J， SHEN B. Dung beetle optimizer： a new meta-heuristic algorithm for global optimization［J］. The Journal of Supercomputing， 2023， 79（7）： 7305-7336.
26	ABDEL-BASSET M， MOHAMED R， SALLAM K M， et al. Light spectrum optimizer： a novel physics-inspired metaheuristic optimization algorithm［J］. Mathematics， 2022， 10（19）： No.3466.
27	SEYYEDABBASI A， KIANI F. Sand cat swarm optimization： a nature-inspired algorithm to solve global optimization problems［J］. Engineering with Computers， 2023， 39（4）： 2627-2651.
28	NIU Y， YAN X， WANG Y， et al. An improved sand cat swarm optimization for moving target search by UAV［J］. Expert Systems with Applications， 2024， 238（Pt E）： No.122189.
29	LIU H， WEI J， XU T. Community detection based on community perspective and graph convolutional network［J］. Expert Systems with Applications， 2023， 231： No.120748.
30	BLONDEL V D， GUILLAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks［J］. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008（10）： No.P10008.
31	WANG X， JIN C. Image encryption using Game of Life permutation and PWLCM chaotic system［J］. Optics Communications， 2012， 285（4）： 412-417.
32	WANG M， WANG J S， LI X D， et al. Harris hawk optimization algorithm based on Cauchy distribution inverse cumulative function and tangent flight operator［J］. Applied Intelligence， 2022， 52（10）： 10999-11026.
33	GIRVAN M， NEWMAN M E J. Community structure in social and biological networks［J］. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）： 7821-7826.
34	BATAGELJ V， MRVAR A. Pajek datasets［DS/OL］. ［2023-12-26］..
35	OPSAHL T. Triadic closure in two-mode networks： redefining the global and local clustering coefficients［J］. Social Networks， 2013， 35（2）： 159-167.
36	PENG P， NI Z， WU Z， et al. Research on incentive strategy based on service quality in spatial crowdsourcing task allocation［J］. Journal of Intelligent and Fuzzy Systems， 2022， 43（5）： 5551-5566.
37	WU G， CHEN Z， LIU J， et al. Task assignment for social-oriented crowdsourcing［J］. Frontiers of Computer Science， 2021， 15： No.152316.
38	WU D， RAO H， WEN C， et al. Modified sand cat swarm optimization algorithm for solving constrained engineering optimization problems［J］. Mathematics， 2022， 10（22）： No.4350.

[1]	刘世梁, 王义, 马应龙. 考虑社区规模不平衡的非重叠社区检测[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3396-3402.
[2]	张佩瑶, 付晓东. 防恶意竞价的众包多任务分配激励机制[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 261-268.
[3]	孙亚男, 吴杰宏, 石峻岭, 高利军. 改进自组织映射的多无人机协同任务分配方法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1551-1556.
[4]	邓辅秦, 黄焕钊, 谭朝恩, 付兰慧, 张建民, 林天麟. 结合遗传算法和滚动调度的多机器人任务分配算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3833-3839.
[5]	彭鹏, 倪志伟, 朱旭辉. 基于用户满意效用的空间众包任务分配方法[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3235-3243.
[6]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 《计算机应用》唯一官方网站, 2021, 41(8): 2232-2241.
[7]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[8]	陈吉成, 陈鸿昶. 基于张量建模和进化K均值聚类的社区检测方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3120-3126.
[9]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[10]	李春英, 汤庸, 肖政宏, 李天送. 学术社交网络中的权威学者推荐模型[J]. 计算机应用, 2020, 40(9): 2594-2599.
[11]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.
[12]	韩俊樱, 张振宇, 孔德仕. 移动群智感知中面向用户区域的分布式多任务分配方法[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 358-362.
[13]	秦海燕, 章永龙, 李斌. 社会网络下分配众包任务的真实机制[J]. 计算机应用, 2020, 40(10): 3019-3024.
[14]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
[15]	张兴盛, 余敦辉, 张万山, 王晨旭. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用, 2019, 39(5): 1357-1363.

融合社区检测的协作众包任务分配方法

Collaborative crowdsourcing task allocation method fusing community detection

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 38

相关文章 15

编辑推荐

Metrics