Multi-Agent Based Team Formation In Heterogeneous Social Networks

Team formation allows individuals to work together to produce a higher quality task than a single individual does. The success of completing a team task not only depends on how professional the team members are, but also depends on how efficiently these team members can collaborate with each other. Therefore, a key challenge of team formation is how to build such a professional and collaborative team of individuals.With the widely use of social software, social networks (SNs) provide good opportunities for addressing this professional and collaborative team formation problem. On the one hand, due to the popularity of mobile devices, such as smart phones and iPad, there are thousands of users available online in SNs and suitable for the tasks, which can help to build professional teams. On the other hand, the positive social connection among individuals, such as the friendships and the partnerships on common project previously, is often a good indicator of effective collaboration. Motivated by these two advantages, team formation in SNs is studied.However, due to the openness, autonomy and heterogenicity, there are also challenges for team formation in SNs. On the one hand, from the perspective of individuals,1) individuals are untruthful and might provide the incorrect private information, such as exaggerating his skill level, social connections and working cost to achieve a higher payoff; 2) individuals have heterogeneous objectives where the task requester wishes to build a professional, collaborative and ecomical team and the individual wishes to the join a team and provides certain skills to team tasks for maximizing his own payoff. On the other hand, from the perspective of the SNs,3) connected individuals have heterogeneous collaboration efficiency and this kind of collaboration efficiency is dynamically changed during team formation; 4) the mesoscopic community sturcure in the SNs and inidividuals have heterogeneous community attributes, the global organization of many SNs is constituted of communities where individuals have denser and better interactions with their intra-community members than with the inter-community members. To address these emerging issues brought by the heterogeneity of individuals in social team formation, including 1) how to guarantee truthful behavior,2) how to satisfy individuals’confilit objectives,3) how to adaptive dynamically changed collaboration efficiency and 4) how to facilate the community structure, multiagent techniques are utilized and advanced and the main contributions are summarized as follows.1) Considering the untruthful individuals that can provide the unreal private information, a multiagent game-theoretic incentive mechanism is proposed. The proposed mechanism pays each individual an extra payment that is independent with his private information, thereby eliciting each individual to provide his truthful private information. Theoretic analyses and experimental results demonstrate that each individual can achieve the highest payment by declaring his private information truthfully and the proposed mechanis applies well to large scale applications.2) Considering the individuals have heterogeneous goals, a multiagent negotiation-based team formation model is proposed. This model designs different negotiation strategies for different individuals. For the requester, the model helps him decide which worker to employ, which skill to exploit; and for the worker, the model helps him decide which team to join and how much to be paid. Theoretic analyses demonstrate that, the requester can form the optimal professional and collaborative team that requires the minimal payment. Experimental results demonstrate that the proposed model can form the more economical teams while consuming the less team formation time.3) Considering the heterogeneous collaboration efficiency and its dynamics, a mobile agent-based distributed team formation method is proposed. This method assigns a mobile and cooperative agent to each subtask. These mobile agents are used to assist their assigned subtasks to search the suitable team of individuals. Furthermore, these mobile agents can cooperate with each other by coalition formation to adapt network structure dynamics. Theoretic analyses demonstrate that the proposed method can always converge to a stable solution in polynomial time. Moreover, the final stable solution can guarantee good team collaboration efficiency and load balancing. Experimental results demonstrate that compared with traditional centralized static methods, the proposed mobile agent-based team formation method not only can form the professional, collaborative and load balancing teams, but also adapt well to network dynamics.4) Considering the SNs consisting of communities and the individuals have heterogeneous community attributes, a community-aware team formation model is proposed. This model first contrains the individuals can only form teams with the individuals that belong to the same community. Under this intra-community cooperation constraint, a heuristic team formation method is proposed by taking full advantage of the skills of the overlapping individuals. Theoretic analyses first demonstrate that the proposed heuristic have a high approximation ratio compared with the optimal solution on social welfare and then provide a sufficient condition on which the proposed heuristic can achieve the optimal social welfare. Experimental results demonstrate that compared to the global-aware and neighbor-aware team formation models, the proposed model can form more collaborative teams while achieving considerable social welfare.