任务分配乃社交网络的重要研究问题之一。一般地,任务的完成质量主要由参与人员的技能水平决定。但是,仅考虑技能水平的任务分配,可能引起各自为战,导致完成质量不高。因此,综合考虑技能水平与协作成本的任务分配方法,能为任务的完成质量提供有效保障。由于执行目标的不同,任务分为协作型任务与竞争型任务。协作型任务需要参与人员精诚合作,为实现一个共同的目标而努力,如嫦娥四号的发射;而竞争型任务需要参与各方既斗争又合作,为了结果的公平性而权衡多种影响因素。显而易见,协作型任务的分配应考虑参与人员的技能水平,并最小化参与人员间的协作成本;竞争型任务的分配不但考虑参与人员的技能水平,还应同时考虑参与人员的代表性,最大化参与人员间的协作成本,高的协作成本保证结果的公平性。本文以社交网络为研究背景,重点关注协作成本与任务完成质量,对社交网络的任务分配问题展开了较为系统的研究,主要的工作成果体现在以下几个方面:1)完成质量最优化的协作型任务分配算法:基于概念格理论,发现超大规模在线社交网络中的小团体,利用小团体成员间的强联系属性,结合协作型任务的内在需求,提出一个完成质量最优化的协作型任务分配算法。将协作型任务分配问题建模为一个组合优化问题,并证明了该优化问题具有NP-hard特性,进而提出一个启发式算法进行求解,算法的时间复杂度为t。2)成员影响力与协作成本联合优化的竞争型任务分配方法:综合考虑候选成员的代表性、技能水平与协作成本,提出面向竞争型任务的有效分配算法。考察基于概念格理论生成的小团体,每个小团体中影响力最大的成员作为最佳备选,并权衡候选人员的协作成本,以保证任务执行结果的公平性。将竞争型任务分配问题进行建模,形成了相应的组合优化问题,并证明该组合优化问题具有NP-hard特性,进而提出一个成员影响力与协作成本联合优化的启发式算法对问题进行求解,算法的时间复杂度为。3)为证实所提算法的有效性,本文使用真实数据集进行验证,并与贪心算法进行比较,本文所提算法在组内协作成本,组内最小协作成本、成员规模、运行时间等方面具有更佳性能。