Collaborative crowdsourcing task allocation method fusing community detection

doi:10.11772/j.issn.1001-9081.2024030274

Journal of Computer Applications ›› 2025, Vol. 45 ›› Issue (2): 534-545.DOI: 10.11772/j.issn.1001-9081.2024030274

• Advanced computing • Previous Articles

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)

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

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

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

通讯作者: 倪志伟
作者简介:胡林波（1997—），男，江西吉安人，硕士研究生，主要研究方向：智能计算、空间众包
程家乐（2000—），男，安徽淮南人，硕士研究生，主要研究方向：深度学习、路径规划
刘文涛（1997—），男，安徽合肥人，博士研究生，主要研究方向：深度学习、智能计算
朱旭辉（1991—），男，安徽阜阳人，讲师，博士，主要研究方向：深度学习、智能计算。
基金资助:
国家自然科学基金资助项目(72171073);安徽省科技重大专项(201903a05020020)

Abstract

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

摘要：

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

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

CLC Number:

TP301.6

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.

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

Figures/Tables 12

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

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

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

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

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

Tab. 1 Details of examples

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

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

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$ 的取值根据不同数据集大小设置相应的范围

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$ 的取值根据不同数据集大小设置相应的范围

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

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

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

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

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

References 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]	Xinrui LIN, Xiaofei WANG, Yan ZHU. Academic anomaly citation group detection based on local extended community detection [J]. Journal of Computer Applications, 2024, 44(6): 1855-1861.
[2]	Shiliang LIU, Yi WANG, Yinglong MA. Non-overlapping community detection with imbalanced community sizes [J]. Journal of Computer Applications, 2024, 44(11): 3396-3402.
[3]	Lin ZHOU, Yuzhi XIAO, Peng LIU, Youpeng QIN. Community mining algorithm based on multi-relationship of nodes and its application [J]. Journal of Computer Applications, 2023, 43(5): 1489-1496.
[4]	Fuqin DENG, Huanzhao HUANG, Chaoen TAN, Lanhui FU, Jianmin ZHANG, Tinlun LAM. Multi-robot task allocation algorithm combining genetic algorithm and rolling scheduling [J]. Journal of Computer Applications, 2023, 43(12): 3833-3839.
[5]	Xiangyu LUO, Ke YAN, Yan LU, Tian WANG, Gang XIN. Nonuniform time slicing method based on prediction of community variance [J]. Journal of Computer Applications, 2023, 43(11): 3457-3463.
[6]	LI Zhanli, LI Ying, LUO Xiangyu, LUO Yingxiao. Local community detection algorithm based on Monte-Carlo iterative solving strategy [J]. Journal of Computer Applications, 2023, 43(1): 104-110.
[7]	Jun HU, Zhengkang XU, Li LIU, Fujin ZHONG. Network embedding method based on multi-granularity community information [J]. Journal of Computer Applications, 2022, 42(3): 663-670.
[8]	Peng PENG, Zhiwei NI, Xuhui ZHU. Task allocation method of spatial crowdsourcing based on user satisfaction utility [J]. Journal of Computer Applications, 2022, 42(10): 3235-3243.
[9]	RAN Jiamin, NI Zhiwei, PENG Peng, ZHU Xuhui. Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution [J]. Journal of Computer Applications, 2021, 41(3): 794-802.
[10]	LI Ping, WANG Fen, CHEN Qidong, SUN Jun. Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem [J]. Journal of Computer Applications, 2021, 41(3): 803-811.
[11]	Jicheng CHEN, Hongchang CHEN. Community detection method based on tensor modeling and evolutionary K-means clustering [J]. Journal of Computer Applications, 2021, 41(11): 3120-3126.
[12]	YANG Wei, LI Ran, ZHANG Kun. Task allocation optimization for automated guided vehicles based on variable neighborhood simulated annealing algorithm [J]. Journal of Computer Applications, 2021, 41(10): 3056-3062.
[13]	LI Chunying, TANG Yong, XIAO Zhenghong, LI Tiansong. Influential scholar recommendation model in academic social network [J]. Journal of Computer Applications, 2020, 40(9): 2594-2599.
[14]	LUO Xiangyu, LI Jianan, LUO Xiaoxia, WANG Jia. Improved community evolution relationship analysis method for dynamic graphs [J]. Journal of Computer Applications, 2020, 40(8): 2313-2318.
[15]	YU Dunhui, YUAN Xu, ZHANG Wanshan, WANG Chenxu. Spatiotemporal crowdsourcing online task allocation algorithm based ondynamic threshold [J]. Journal of Computer Applications, 2020, 40(3): 658-664.

Collaborative crowdsourcing task allocation method fusing community detection

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 38

Related Articles 15

Recommended Articles

Metrics