Effective team formation in collaboration networks using vertex and proficiency similarity measures

Abstract

Discovering an effective team of experts toward accomplishing the specific task in social networks has been considered in many real projects. The communication and collaboration among the members and the small cardinality of the team are in the opposite direction to success of the projects. In this paper, we show that the type of a similarity function is also impressive. Its importance is revealed on determining what similar or dissimilar experts should be selected or rejected in the process of the assignment. Considering the graph of underlying social network as conceptual social networking websites, we attribute the team formation problem as a vertices similarity environment based on their common neighbors regarding their co-authored papers. Also, the implicit similarities are used with respect to inattention of additional intermediates between any two nodes in the graph. In addition, taking inspiration from human–human interactions, using just the implicit vertex similarities propose a collaborative recommendation that is based on the team formation framework. They can also identify effectors in social networks established by the structural equivalence relation. Thus, they make the algorithm faster on searching for members of the team. Moreover, the proficiency similarity measures of authors are considered as their potential characteristics that measure their skillfulness level and real contribution corresponding to the required skill. The combination of similarity measures in the cost function causes the algorithm to search the more effective team specially in equal situations. The experimental results on DBLP co-authorship graph show the effectiveness of using the new similarity measures in the proposed method.

Keywords

Social networks team of experts similarity measures

1. Introduction

A social network is a complex network presenting social interactions between people [38]. Recently, online social networking web sites such as Facebook, Twitter,1

¹
www.twitter.com.

MySpace, LinkedIn,2

www-linkedin-com.web.bisu.edu.cn.

Xing3

www.xing.com.

etc. have become so popular and applicable. Infact, these networks improve communications of people and society and let them to share their opinions, shopping and etc. all around the world. Social networks like many other networks show several interesting properties such as high network transitivity [39], power-law degree distributions [4], the existence of repeated local motifs [27] and groups structure [29]. Such highly informative environments can help experts to improve their collaborations. Therefore, finding qualified people and teams for a highly specific purpose can be achievable. In order to reduce costs, increase speed and improve quality and agility under the effects of changing business in social environments, organizations have flattened, and teams have emerged as a key organizational tool. Integrated product teams, task force teams, management teams, self-directed teams, multi-functional teams, leadership teams, quality improvement teams and venture start-up teams are just a few examples of how teams are used as an effective response to a range of business challenges. Clearly, teams have their problems. There have been enough studies on teams untill now to understand the critical phases that teams go through during their formations and developments. What is rarely considered as a cause of team failures is flaws in the initial configuration and structure of the team itself. Several researchers try to present a high-performance algorithm to find the desired team. Salas et al. define a team as a distinguishable set of two or more people who interact dynamically, interdependently and adaptively toward a common and valued goal/object/mission which was assigned by specific roles or functions to perform with a limited life span of membership [32]. Thus, teams are the special type of groups that are interdependent from each other and play specific roles for different team members. However, members of the team may be expert in different skills, but they can complement each other when they collaborate for the specific project according to their deadlines. Therefore, the measure of cooperation in teams is more significant than groups. Although members of the team maybe separate from each other, they can be selected from disconnected (variant) groups in the social graphs. The team’s purpose and the nature of the performed work are greatly influenced by a team’s configuration, formation and development. Likewise, in this paper, the appropriate team of experts is determined based on a given task as a set of skills.

In the past few years, finding a team of experts has become one of the most important and popular subjects in the realm of social network analysis. It is necessary for many companies or departments to detect persons who have enough relevant experiences and expertise to accomplish a given specific task. Consequently, the success of the project is not only defined by the accomplishment of the task but also influenced by the communications and collaborations of team members that play significant role in the performance of the project. So, a project manager tries to evaluate and improve these relations. In addition, it is desirable to achieve a minimum possible cost in the process of accomplishing the project. Also, selecting two experts with respect to their previous collaborations and skills would greatly influence on the final team in real projects. Thus, considering the skill grading of selected individuals can affect the efficiency and quality of the project.

There are several investigations on detecting a team of experts among the works done recently by Lappas et al. [21]. The authors propose the cost function as a diameter of the selected sub-graph to estimate the communication costs of teams. They suggest the connection weights calculated by the Jaccard similarity measure. However, in present paper, we want to investigate other similarity measures for the final assignment. The proficiency and vertex similarity measures that indicate the basic concept of relationships and collaborations in the social network are considered. Suppose that, there is a set of candidates $V = {1, 2, \dots, n}$ where each candidate, $v_{i}$ , is an expert with a set of skills $S_{v_{i}}$ . The skillfulness level of each individual, $v_{i}$ , per each skill, $s_{k}$ , is specified by proficiency similarities, and their collaborative ability is calculated by vertex similarities. It is supposed that the individuals are organized as a weighted and undirected graph $G (V, E)$ . The weights of edges in graph G show the interaction between individuals. It is used as a measure reflecting how the corresponding individuals can communicate and collaborate closely. Here, the simple weight of the edge between two specific authors indicates the number of their co-authored papers. Given a task T which includes some required skills $s_{k}$ , our final aim is to find a team of individuals $V^{'} \subseteq V$ where each skill in T is covered by at least one expert.

Fig. 1.

Overal design of proposed cost function. Basic similarity measures and their mixed mode are used in this paper.

Figure 1 depicts the overall design of the new cost function in regard to the new similarity measures. As it is shown, the proposed cost function utilizes four factors in practical mode: first, the diameter distance that uses Jaccard or Cosine similarity measures based on the number of co-authored papers. Second, the implicit vertex similarity that contains the similarity measures based on the inattention of additional intermediate co-authorship concept. Third, the proficiency similarity that indicates the skillfulness level of each author according to the given task. The last one is the JaccardPearson skill grading which considers both the skill profile of the author and his contribution measure in the network. Moreover, combinations of these similarities are used in the cost function for searching more potential experts in a process of the algorithm. Here, Jaccard similarity, Cosine similarity, Topology Overlap similarity and the relation strength similarity are defined as vertex similarity measures. Furthermore, the contribution of skill (COS) and the significance of interests of skill (SOI) for the specific expert are determined as proficiency similarity measures. All of these similarity measures are charted in Fig. 2 and studied in details in Section 3.3.

Fig. 2.

Overal design of proposed cost function in details. The explicit similarity implies the direct connection of authors in regard to their co-authored papers. The implicit similarity is based on the virtual connection according to common neighbors. The proficiency similarity and JaccardPearson skill grading indicate the measure of author’s expertise and contributions.

The main contribution of the proposed method is the comparisons of the team performance upon different similarity functions and the combination of these functions. Basically, the Jaccard similarity function which is mentioned by Lappas et al. is used in this paper. In this function, experts are comprised based on their more quantitative common co-authored paper, and favorite team is formed by the lowest cost. It means that the comminucation cost is reduced when two members have more common co-authored paper. This similarity function may be sufficient for an investigation of the algorithm which is used by Lappas et al. [21]. However, this similarity function, Jaccard, is not adequate to introduce team members who are skilled and efficient specially in the equal conditions. Hence, we try to improve the team formation problem by using implicit similarity functions based on common neighbors. Also, the proficiency similarity function of each member is presented based on required skill. Actually, this team is not only connected based on the number of co-authored papers but also investigated by other prospectives such as level of skill and degree of co-neighbors.

Suppose that person A wants to choose one between person B and C as his next teammate. The one who has more co-authored papers is chosen to reduce the communication cost. In the previous algorithm, the next teammate is chosen randomly when they have similar communication cost. However, in this paper, the one who has shared parameters from other perspectives is selected. In fact, based on the social network structure, it can be stated that two individuals are more similar if they have more co-neighbors. Actually, there exist more individuals who are collaborating and trusting on them. Therefore, it seems that these two members has more commons and similarities in other skills in addition to their current skill. Also, they are capable for further collaborations. Hence, this factor is highly important. Moreover, in the next step, the personal specification of these members is considered. This character can be evaluated by the degree of favorite and/or contribution rank of each member on the required skill. Then, it can be possible to prefer some members rather than others according to this parameter.

It is noted that the proper position of these similarity functions is in the cost function. As the other example, suppose that person X is selected and skilled in our required task in the initial process. The algorithm should gradually improve to find proper team members as the teammates of X. So, person X should find his next skilled teammate (like person Y) through his connected neighbors and add these connected neighbors (i.e. path) to his related team. On the other hand, if these two members (person X and Y) are virtually connected, the cost of the final team will be decreased. By forming the virtual network in the initial step, the people are virtually linked based on the rank of their common neighbors. So, the algorithm will find team members faster and more economic in this new network since the main effectors are only inserted. It is noted that this advanced team is formed when the priority of diameter distance is assumed zero in the cost function, and just the implicit similarity for each pair of nodes are initially defined. In this method, first, the virtual network is constructed regards to the RSS measure of each two nodes in the graph. Then, the algorithm is implemented on this virtual graph and forms the final team. The similarity function of each skill is used for quality enlargement, and it does not interfere to its contributions. Although the members of this team may not directly connect to each other, the final team is expert and highly contributed. Then, we can use this team as a good framework for recommending of effectors to each other for collaboration in the future. These effectors are chosen according to their level of abilities, skills, contributions, shared papers and neighbors. Therefore, they are more reliable and can be recommended as proper co-workers. This network can be organized as an efficient social network in its next generation.

Figure 3(a) is given here to clarify our contribution comprehensively. We have an expert social graph where each node represents an expert, and the undirected weighted edges indicate the existence of communication between corresponding nodes. The ${s_{k}, n_{k}}$ shows that the size of skill $s_{k}$ for related author is $n_{k}$ . Suppose, we have a specific task $T = {s_{1}, s_{2}}$ with some required skills that should be supported by at least one expert. The Lappas Diameter RaresFirst algorithm solutions for this graph are $v_{D} v_{A} v_{B}$ , $v_{D} v_{A} v_{C}$ , $v_{E} v_{A} v_{B}$ , $v_{E} v_{A} v_{C}$ sub-graphs. Although it seems that $v_{F} v_{B}$ can support the required task, the connected graph to disconnected one is preferred. In this case, connected groups indicate that the people in the same community or department can collaborate easier than those who work in different divisions. Therefor, we have four equal solutions with diameter of length 7 in this case. Now, the main question is which team is really the best one?

Regarding the proficiency similarity, we immediately conclude that $v_{B}$ is better than $v_{C}$ because of its’ skillfulness level of skill $s_{2}$ . So, subgraph including $v_{B}$ to $v_{C}$ is preferred. The last contrast is between $v_{D} v_{A} v_{B}$ and $v_{E} v_{A} v_{B}$ . Considering the vertex similarity that marks the co-neighbor objective, the two nodes have more similarity if they have more common neighbors. $v_{E}$ is preferred than $v_{D}$ because it has one more co-neighbor, $v_{H}$ . Thus, we realize $v_{E} v_{A} v_{B}$ is our best final team.

The other main contribution is depicted in Fig. 3(b). In this graph, implicit connections between nodes are assigned by assisting their intermediates. In the real scenario, when author $v_{B}$ and $v_{D}$ collaborate with author $v_{A}$ , we could match them as new recommended collaborators. More specifically, we could virtually match them and let team formation process to be accomplished. When the last team is selected, it is a good framework for recommending the effective experts to each other for collaborating in the future. The $v_{E} v_{A} v_{B}$ is a good team, but its influential members to accomplish the required task are $v_{E}$ and $v_{B}$ . So, we could also define our final team as $v_{E} v_{B}$ . The other contributing factor to success of the project is the size of the final team. It seems to be much more effective to discover the smallest team because of its impressive effect on the expenses of the project. Hence, using implicit vertex similarity measures help us to discover the highly briefly effective team of experts in the given social graph. This ability is more clarified by vertex similarity measures in Section 3.3.

Here, several factors that influence on performance of the team are presented. The effectiveness of the team of experts is considered by various parameters and perspectives. Corresponding to our viewpoint, these factors are categorized as follows: first, the communication cost of the team should be minimized as much as possible. In fact, this function shows the similarity measure of each member. For example, Lappas et al. depicted that the communication cost is reduced when two people co-author more papers. Second, the size of the team must be reduced since it often has a positive effects on the expenses of a project. Third, connected teams should be preferred rather than disconnected ones. It means that the algorithm first finds the team which is connected to accomplish the required task, otherwise the disconnected one is chosen. Furthermore, the chosen members must be highly expert and skilled to support the required task. This factor can be the significance of interest and the quantity of contribution of task. Finally, the members who are highly communicated to other members are preferred. In fact, the members who have more collaborators are more trusty and effective in social networks. This parameter is depicted by more co-neighbors in our paper. The mentioned parameters of effectiveness are used in experiments and formulation of the problem, and these recommended methods show their performance in quantitative results.

The remainder of this paper is organized as five sections. The Section 2 gives brief reviews on the related works in the field of team formation and similarity measures. The Section 3 introduces the proposed framework as follows: first, the problem definition and preliminaries are defined, then suggested similarities including vertex, proficiency and skill grading similarity measures are mentioned. The experimental results are presented in the Section 4, and finally we conclude the paper in the Section 5.

2. Related work

The related works can be classified in two perspectives: (1) the previous studies on the team formation problem, and (2) the related works on proposed similarity measures which are used in this paper.

2.1. Team formation

The issue of selecting project team members has many usages in real projects. Particularly, it is more crucial for companies, R&D-oriented institutes and human resource management departments. For company’s activities, in-house staff members are organized in teams and departments. These organized teams perform as intended units and influence on the performance of the entire organization [26]. Team formation has great effects on creating organizational performance, so it becomes a very critical issue in the modern company environment. The R&D activity in institutes is typically run with the same approach as the project team management, and the main part of the organization is its related team [37]. However, the success of a project highly depends on human resources rather than the various resources required for the project. Like a project team, the task force team (TFT) organized for companies to carry out certain tasks is also characterized by its performance. They are highly depended on the organization of team members. Actually, being a functional team in companies, a project team in research organizations, or a TFT for a specific purpose, the team performance depends upon whether team members are well organized and collaborating or not. Wi et al. refer a team formation as the basis of a project team in a research organization. This viewpoint can be consistently applied to a functional team and TFT in companies [40].

A considerable number of works in the literature have been devoted to study the team formation problem. In these works, the authors study the team formation problem by transforming it into an integer programming. Simulated annealing [5], branch-and-cut [42] and genetic algorithm [40] are used to find an optimal match between individuals and requirements. Chen et al. use a psychological test to form a team by estimating the individual’s interpersonal relational attributes and their personalities [10]. The drive and temperament of individuals for achieving the fine quality of the team are evaluated by Fitzpatrick et al. [14]. However, Gaston et al. show the correlation between different graph structures and performance of a team, but they do not consider a computational problem of finding the team formation [15]. Cheatham et al. consider the structure of the social network by collecting the neighbors surrounding each skill in a social-concept [8]. All of these works have been done based on psychology, and they do not pay attention to the graph structure among individuals and the communication cost among them. The specific techniques required to estimate the strength of relationship among individuals are valuable researchs that have been pursued in other research works [23,41]. However, these directions of researches are used for general purpose and do not consider the team formation problem and its’ constrains. Backstrom et al. provide useful information about different aspects of the team formation in social networks [3]. In Ref. [2], the authors study a version of the team formation problem that the goal is to balance the load of individuals (i.e. the number of projects one is assigned to). However, this version of the problem overlooks the social collaboration and cost altogether.

The team formation problem in the presence of a social network of individuals is first addressed by Lappas et al. by considering the communication cost function [21]. They also prove that the problem of finding this kind of teams is NP-hard. In their work, they propose the RarestFirst and EnhancedSteiner algorithm to solve the team formation problem based on diameter and minimum spanning tree (MST) respectively. In RarestFirst approach which we use here as the basic algorithm, it first estimates each required skill’s supporter. Then, the skill with rarest sponsors is determined. Afterward, for each of its candidates, a sub-graph is defined by investigating the closest connected individuals in other support sets. In the last step, it selects the sub-graph with the minimum communication cost by using the diameter metric. The problem of finding a team of experts with a leader is introduced in Ref. [17] by Kargar et al. They also determine the modified cost function as the sum of distances of the expert team. The sum of the shortest distances between experts is responsible for each pair of skills. C. Li et al. in Ref. [24] propose a grouping graph method that condenses the expert information to a grouped graph according to the required skills. They extend the EnhancedSteiner algorithm of Lappas et al. to its generalized version for generalized tasks. Also, they offer a Generalized EnhancedSteiner algorithm for generalized tasks by associating each required skill with a specified number of experts.

2.2. Proposed similarity measures

Matching the proficiency level of individuals are considered in many communities. These studies are on individuals who highly satisfy the task requirements. Thus, the expert level is based on the number of evaluated residual skill sets which are or are not satisfied by related individuals. To formulate these applications, Zakarian et al. [42] and Boon et al. [6] aim to handle the problem with a fuzzy approach. Zakarian et al. in Ref. [42] propose an analytical model for selecting the multi functional teams that prioritize ‘team members’ based on task requirements. Boon et al. in Ref. [6] enhance the quality of the team by combining the qualities of candidates with functional requirements in order to assign the right individuals to right teams. In another study, to measure the suitability of the individual’s skill set for performing a task, Korwin et al. [20] address an algorithm that considers skills of candidates and utilizes fuzzy set theory to evaluate compatibilities of skill sets. In Ref. [11], forming a qualified and attributed team is presented where each attributed team satisfies at least the minimum requirements and required skills for a specific task. In this case of study, a fuzzy mathematical programming is modeled, and a solution algorithm based on the simulated annealing method is proposed for building an effective and qualified attributed team. Liu et al. [28] measure the similarity between users based on the correlation between their rankings of items rather than the rating values. Moreover, they propose a new collaborative filtering algorithm for ranking items based on the preferences of similar users. Candillier et al. in Ref. [7] give guidelines and discuss about combining traditional similarity measures to design a new weighted similarity criterion in the field of recommended systems.

There are several areas like social network analysis [22], information retrieval in World Wide Web [19] and collaborating filtering [34] that use vertex similarity measures to determine the similarity of two vertices based on the structure of the network. Some measures compute the number of common neighbors. Jaccard similarity [35], Cosine similarity [33] and Topology Overlap similarity [30] measures are usually used in many cases. These similarities indicate that two vertices have more similarities if they have more common neighbors. Although they consider only local information, they are computationally efficient.

Furthermore, the global similarity measures can be used for the vertex similarity measures. Although they look for the global network structure and consider extra appearance of the network, their computational complexity is prohibitive. Additionally, small changes in the network such as adding or deleting one node would affect the global structure based on similarities of whole network. So, using global structures is not feasible for large scale dynamic networks. Therefore, Chen et al. in Ref. [9] introduce the relation strength similarity function which is the same as global structures in large degree and local measures based similarities in low degree. The relation strength similarity shows the similarity of two vertices based on their common neighbors, and the separation degree marks the scale of separation between two vertices. Thus, by balancing the degree of separation, the compromise between local and global information search is achieved. The details of relation strength similarity measure are studied in Section 3.3.

Here, we use a skill grading method for achieving the effective team based on given weighted social network and communication cost. To achieve a specific weighted similarity measure, a formula is proposed by combining Pearson and Jaccard measures to benefit their complementarity. Pearson correlation corresponds to the Cosine deviation from the mean and considers only common attributes. On the contrary, Jaccard similarity measures the overlap that two individuals share with their skills. However, it does not take into account the different uses of rating scale by various individuals. So, the combination of these two traditional measures with the simple production is useful to benefit from their advantages.

3. The proposed framework

In this section, first, the problem definition of our work and preliminaries are completely reviewed. Consequently, our framework is presented.

3.1. Problem statement

As being humans, it is necessary for all of us to make social interactions with each other. None of us like to be alone, and we often have incentives to establish collaboration with everyone that has a common behavior, ethics, social interactions, and specially skill profile with us. This is the reason that we belong to the teams whose members are very similar to us in both real and cyberspace lives. This motivates us to consider the team formation problem in social networks as a play of co-authorship interactions between their constituents, i.e. people.

We indicate similarity measures on our work because they provide rigorous mathematical models of strategic interactions between experts and intelligent authors. Indeed, the fine similarity measure is a good tool to capture both the proficient level of expert’s skill profiles and the strategic interactions among them. It shows the influence of our contribution on the expert social behavior. According to this fact, the team formation problem is formally defined as follows: Given the social network graph $G (V, E)$ , the skill set of experts and a task T which includes required skills $s_{k}$ , the problem is finding a set of experts $V^{'} \subseteq V$ who can support the required skills. To be specific, a sub-graph $G [V^{'}]$ is formed by these parameters: (1) all of the required skills in the given task should be accomplished by the team, and (2) the total communication cost denoted by $CC (V^{'})$ among selected individuals must be minimized as much as possible.

3.2. Preliminaries

The necessary terminologies for the remaining of the paper are shown in Table 1.

Table 1
Terminologies used in this paper

Symbol	Definition
$G (V, E)$	Undirected and weighted graph
n, m	Number of individuals and skills
$v_{i}$	Author i
$N_{i}$	Set of neighbors of author i
T	Given task consisting of required skills
S	Set of skills
$s_{k}$	Skill k
$S_{v_{i}}$	Set of skills of author $v_{i}$
$Supp (s_{k})$	List of authors who can support the skill $s_{k}$
$P_{i}$	Set of papers co-authored by author i
$P_{i}^{s_{k}}$	Set of papers co-authored by author i for $s_{k}$
$f_{i}^{k}$	Number of appearing times of $s_{k}$ in $P_{i}$
$path (v_{i}, v_{j})$	A simple path from $v_{i}$ to $v_{j}$
$d (i, j)$	Dijkstra’s shortest path along i and j
$D_{i}^{'}$	Diameter of subgraph constructed with $v_{i}$
$R (i, j)$	RSS between i and j
$R_{p m}^{*} (i, j)$	RSS between i and j through path $p m$
$num (i, j)$	Number of nodes along shortest $path (i, j)$
ϵ, γ, α, β	Balanced parameters for different cost function

The social network is modeled as an undirected and weighted graph $G (V, E)$ , where the vertices $V = {v_{1}, v_{2}, \dots, v_{n}}$ are experts, and the edges E represent collaborations in co-authorship network. The edge weight w describes the cost (distance) between any two experts. The small-weight edges show that the experts have more frequent collaborations than high-weight edges. Here, we suppose that graph G is connected. However, in the case of graphs with disconnected components (i.e., dissimilar components), we could also add very high-weight edges between every pairs of nodes that belong to different disconnected components. This weight is much higher than the sum of all pair-wise shorted paths in each connected component. Moreover, it is used when there are some disconnected teams in the network in addition to connected ones.

Furthermore, it is assumed that we have a set of m skills, $S = {s_{1}, s_{2}, \dots, s_{m}}$ , where each expert has a skill set $S_{v_{i}} \subseteq S$ . We denote $s_{k} \in S_{v_{i}}$ if individual $v_{i}$ has skill $s_{k}$ . Also, a subset of individuals $V^{'} \subseteq V$ has skill $s_{k}$ if there is at least one individual in $V^{'}$ associated with $s_{k}$ . A task T is simply a subset of skills S required to accomplish the project. The graph distance function for every two nodes $v_{i}, v_{j} \in V$ is the weight of the shortest path between them in G, denoted by $d (v_{i}, v_{j})$ . The distance between node $v_{i} \in V$ and a set of nodes $V^{'} \subseteq V$ is defined by $d (v_{i}, V^{'}) = {min}_{j \in V^{'}} d (v_{i}, v_{j})$ .

3.3. Framework

3.3.1. Framework foundation

In this section, we formally define our proposed method in details. Finding a team of experts while minimizing the presented communication cost function is proved to be an NP-hard problem in Ref. [21]. So, we cannot hope to compute optimum solutions for our team formation problem. In this investigation, we try to achieve the better team than previous studies with auxiliary parameters. The presented approximated Generalized Diameter algorithm based on diameter distance is proposed the same as the RarestFirst algorithm [21]. It addresses the team formation problem for basic tasks to compute closer optimum teams due to the proposed cost models. In this section, we turn our attention from an improved greedy and incremental method to the modified version of generalized tasks by presenting the Generalized Diameter algorithm in Algorithm 1. In general, the inputs of the algorithm are a graph $G (V, E)$ , where $| V | = n$ , the skill set of individuals and a general task $T = (S, C)$ including a set of some required skills $s_{k}$ . In addition, $T = (S, C)$ is defined by ${(s_{k}, c_{k}) ∣ \forall k, 1 ⩽ k ⩽ q, s \in S, c_{k} is an integer}$ , where $c_{k}$ denotes the required number of experts for $s_{k}$ , and q is the number of required skills for completion of task T. In this paper, $c_{k}$ is assumed as 1 for all skills. It means that each required skill must be supported by at least one expert. As experiments of the generalized task were practiced in the previous paper [13], the focus of the present study is on the effects of the similarity measures on the performance of the selected team.

Identical to previous paper [13], the algorithm works as follows: it first computes the support set $Supp (s_{k})$ for every skill $s_{k} \in T$ , then it picks the $s_{rare} \in T$ with the lowest cardinality of support set $Supp (s_{rare})$ which is formulized as: $\begin{array}{rclr} Supp (s_{rare}) = {v_{\exp} ∣ s_{rare} \in S_{v_{\exp}}}, \\ s_{rare} = \underset{s_{k} \in T}{arg min} | Supp (s_{k}) | . & (1) \end{array}$

Algorithm 1.

The Generalized Diameter algorithm

Among all of the candidates from the set $Supp (s_{rare})$ , the algorithm picks the one that leads to the smallest diameter subgraph. It is done when the selected candidate connects to the closest individual of all other supported groups $Supp (s_{k})$ ( $s_{k} \in T$ and $s_{k} \neq s_{rare}$ ). So, first, the shortest path between each member of $Supp (s_{k})$ and a current expert, $v_{\exp}$ , is calculated (line 11). The algorithm repeats several rounds until the specified number of experts for each required skill is covered (line 13). At each round, among all of the shortest paths between $v_{\exp}$ and each ${Support ∣ Support \in Supp (s_{k})}$ , the minimum one is determined to select the appropriate groupmate for covering the skill $s_{k}$ (line 16). Afterwards, the nodes through this path which has the minimum distance to $V^{'}$ are added (line 17). Then, it is decreased from the required number of experts for skill $s_{k}$ with respect to the skill node $v_{\exp}$ by one (line 18). In the case of realization of covering other required skills by an individual ${v_{j} ∣ v_{j} \in path (v_{\exp}, a^{*}), v_{j} \notin Supp (s_{k})}$ which already added, it is reduced by one from the required experts for skill $s_{w} \in S_{v_{j}}$ , $s_{w} \in T$ . Then, the skill set of individual $v_{j}$ is updated to prevent the algorithm from reviewing the skill ability of $v_{j}$ in the next rounds with regard to skill $s_{w}$ (line 19–21). When all of the required skills are satisfied, the incremental construction of subgraph $V^{'}$ is terminated. Recall that, the diameter of a graph is the largest shortest path between any two nodes in the graph. So, the diameter of the subgraph $V^{'}$ is calculated as $D_{\exp}^{'}$ by determining the maximum of shorted paths of the subgraph which were constructed by node ${v_{\exp} ∣ v_{\exp} \in Supp (s_{rare})}$ (line 27). Finally, among all subgraphs, $V^{'}$ is constructed by $Supp (s_{rare})$ . Then, the algorithm picks the one that leads to the smallest diameter subgraph as $D_{\exp}^{'}$ and extracts corresponding nodes as the final selected team (line 29–30). By this computation, we guarantee that at least the specific required number of experts for covering each required skill in the given task T is selected as an effective and condensed structure.

The simple weight function can be calculated by Jaccard or Cosine similarities which is defined by explicit vertex similarity measures: $\begin{array}{rclr} Jaccard (v_{i}, v_{j}) = \frac{| P_{i} \cap P_{j} |}{| P_{i} \cup P_{j} |}, & (2) \\ Cosine (v_{i}, v_{j}) = \frac{| P_{i} \cap P_{j} |}{\sqrt{| P_{i} | \cdot | P_{j} |}} . & (3) \end{array}$

It is noted that there are several studies which show the Cosine similarity generally performs better than Jaccard similarity in most practical situations [16].

We assume that all of the shortest paths between each pair of nodes, proficiency and vertex similarity measures and all author’s skill grading have been pre-calculated and stored in a hash table. Then, for the graph $G (V, E)$ , the total running time of the Generalized Diameter algorithm is $O (| Supp (s_{rare}) | \times n \times (δ \times | path (v_{\exp}, a^{*}) |))$ . The worst case analysis suggests that the computations of $| Supp (s_{rare}) |$ and $δ \times | path (v_{\exp}, a^{*}) |$ can be done in $O (n)$ time. The δ is the maximum specific required number of experts for each required skill, and it is a constant. Therefore, the worst case running time of the Generalized Diameter algorithm is $O (n^{3})$ . Hence, the $| Supp (s_{rare}) |$ and $| path (v_{\exp}, a^{*}) |$ are much smaller than n, and the total running time of the proposed implementation is much less than this worst case analysis in practice. However, this running time is more than time consuming of RarestFirst algorithm ( $O (| Supp (s_{rare}) | \times n) = O (n^{2})$ ). In addition, it should be noticed that unlike the RarestFirst, the Generalized Diameter algorithm rechecks the added path in each iteration by ensuring whether other required skills are included or not. This improvement prevents Generalized Diameter algorithm from extra discovery to satisfy already required skills and leads to a subgraph with smaller cardinality and diameter. Therefor, it can be performed in an efficient time.

3.3.2. Implicit vertex similarity measures

The vertex similarity measures describe how much two authors are similar regarding their previous co-authorship relations. In addition, their motivations to collaborate in the future are discussed based on the structure of social networks. At first, two well-known similarity measures are defined as Jaccard and Cosine similarity functions. In order to discriminate the last version of the Jaccard and Cosine similarity, we call them VicinityJaccard and VicinityCosine here: $\begin{array}{rclr} VicinityJaccard (v_{i}, v_{j}) = \frac{| N_{i} \cap N_{j} |}{| N_{i} \cup N_{j} |}, & (4) \\ VicinityCosine (v_{i}, v_{j}) = \frac{| N_{i} \cap N_{j} |}{\sqrt{| N_{i} | \cdot | N_{j} |}} . & (5) \end{array}$

Topology Overlap similarity also uses neighborhood information and presented as follow: $TOS (v_{i}, v_{j}) = \frac{| N_{i} \cap N_{j} |}{min (| N_{i} |, | N_{j} |)} .$ (6)

Although global similarity measures consider the whole network, these methods are not feasible for large scale social networks since they have high time complexity. However, Chen et al. [9] suggested a relation strength similarity function (RSS). The RSS of two experts is proportional to the number of their co-authored papers and stated as follow: $R (v_{i}, v_{j}) = \frac{| P_{i} \cap P_{j} |}{| P_{i} |} .$ (7)

The relation strength similarity for two non-adjacent vertices shows that if two authors ( $v_{i}$ and $v_{k}$ ) have a common neighbor as $v_{j}$ , the relation strength similarity of $v_{i}$ to $v_{k}$ is equivalent to the relation strength of $v_{i}$ to $v_{j}$ and the relation strength of $v_{j}$ to $v_{k}$ . Hence, the indirect relation strength similarity from author $v_{i}$ to $v_{k}$ is calculated as follows: $R^{*} (v_{i}, v_{k}) = R (v_{i}, v_{j}) \cdot R (v_{j}, v_{k}) .$ (8)

Suppose that there exists a simple path $p m$ from $v_{i}$ to $v_{k}$ , where the path $p m$ is formed by ${v_{i}, v_{j 1}, v_{j 2}, \dots, v_{j H}, v_{k}}$ . The indirect relation strength similarity from $v_{i}$ to $v_{k}$ through simple path $p m$ is generalized as follows: $\begin{array}{rclr} R_{p m}^{*} (v_{i}, v_{k}) \\ = R (v_{i}, v_{j 1}) \\ \cdot \prod_{h = 1}^{H - 1} R (v_{j h}, v_{j (h + 1)}) \cdot R (v_{j H}, v_{k}) . & (9) \end{array}$

For M distinct paths ${p_{1}, p_{2}, \dots, p_{M}}$ from $v_{i}$ to $v_{k}$ , the relation strength similarity for these two vertices can be defined as the sigma of their RSS through these paths or the maximum RSS of them. $\begin{array}{rclr} RSSsigma (v_{i}, v_{k}) = \sum_{m = 1}^{M} R_{p m}^{*} (v_{i}, v_{k}), & (10) \\ RSSmax (v_{i}, v_{k}) = max R_{p m}^{*} (v_{i}, v_{k}) . & (11) \end{array}$

Fig. 3.

Example of connected graph: (a) Explicit connected graph. (b) Implicit connected graph.

The relation strength similarity measure is asymmetric, i.e.,

R (v_{A}, v_{B})

may not equal

R (v_{B}, v_{A})

as it is defined in Eq. (7). This property is close to the real world scenario. By considering authors

v_{A}

and

v_{C}

in Fig. 3, it seems that the importance of author

v_{A}

v_{C}

is higher than

v_{C}

v_{A}

since

v_{A}

is cooperates with four other authors while

v_{C}

is just connected to

v_{A}

. Moreover, the consideration of the weighted structure of a graph is the other benefit of using RSS like other similarities. For example,

v_{E}

is more important than

v_{H}

for

v_{A}

because of its more co-authored papers. In addition, the RSS value is between 0 and 1 as Chen et al. prove in their paper [9].

Table 2

The proficiency similarity mapping table corresponding to Fig. 3

	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$
$v_{A}$	SOI = 0, COS = 0	SOI = 0, COS = 0	SOI = 2/3, COS = 2/5	SOI = 1/3, COS = 1/9
$v_{B}$	SOI = 0, COS = 0	SOI = 3/5, COS = 3/4	SOI = 0, COS = 0	SOI = 2/5, COS = 2/9
$v_{C}$	SOI = 0, COS = 0	SOI = 1/2, COS = 1/4	SOI = 0, COS = 0	SOI = 1/2, COS = 1/9
$v_{D}$	SOI = 2/5, COS = 2/11	SOI = 0, COS = 0	SOI = 3/5, COS = 3/5	SOI = 0, COS = 0
$v_{E}$	SOI = 2/4, COS = 2/11	SOI = 0, COS = 0	SOI = 0, COS = 0	SOI = 2/4, COS = 2/9
$v_{F}$	SOI = 7/8, COS = 7/11	SOI = 0, COS = 0	SOI = 0, COS = 0	SOI = 1/8, COS = 1/9
$v_{G}$	SOI = 0, COS = 0	SOI = 0, COS = 0	SOI = 0, COS = 0	SOI = 1, COS = 1/9
$v_{H}$	SOI = 0, COS = 0	SOI = 0, COS = 0	SOI = 0, COS = 0	SOI = 1, COS = 1/9

Although RSS is a good option for using in the cost function as it can consider the whole network, its complexity of computing the similarity from one vertex to all other vertices is $O (d^{hole})$ . In this case, d is the average degree of vertices and hole is the size of intermediates (i.e., degree of separation). This complexity is necessary to check all possible paths between each two nodes. Since RSS is an asymmetric approach, we need $O ({nd}^{hole})$ to compute the similarity between all the nodes in the graph. The main computational part of this complexity is depended on the hole quantity. In this paper, we consider this degree value as 3, meaning that one intermediate is considered in RSS formula for the experimental results. Moreover, it is clear that by increasing the hole size, more effective results can be obtained due to consider complete topology of the network.

3.3.3. Proficiency similarity

In this section, solutions for scaling the skill abilities of individuals are discussed. The proficiency similarity measures applied in this paper are the significance of interests of skill (SOI) and the contribution of skill (COS) which are defined as follows: $\begin{array}{rclr} SOI (v_{i}, s_{k}) = \frac{f_{i}^{k}}{\sum_{u = 1}^{| S_{v_{i}} |} f_{i}^{u}}, & (12) \\ COS (v_{i}, s_{k}) = \frac{| P_{i}^{s_{k}} |}{\sum_{w = 1}^{n} | P_{w}^{s_{k}} |} . & (13) \end{array}$

Table 2 represents the sample of skill mapping which is depicted by Fig. 3. Regarding the searching process of the best author to support required skill $s_{4}$ , following results are achieved. Although the SOI of authors $v_{G}$ and $v_{H}$ has a maximum value, their COS is very low. It signifies that we need the skillfulness level of authors with respect to their contribution measure. It means that one author may has many co-authored papers according to the required skill, but it is not enough for selection. Here, author $v_{B}$ or $v_{E}$ is a good candidate for supporting the skill $s_{4}$ . Furthermore, the importance measure of COS and SOI is depended on the given network and how the project manager designs the project. However, it is obvious that if we want to compromise between interest and contribution of the skill, we should balance their degree of importance. Then, the best one is chosen. In this study, the quantity of author’s communications is considered. However, the diameter distance of Lappas et al. [21] does not take this reality in to account. Therefore, based on their work if one author co-authors all of his papers with just one of his neighbors, his diameter distance gains as low as possible. Thus, it seems to be fine despite of his contribution effect. By marking this factor, the effectors are more available in the searching process. So, the more appropriate expert team can be determined. In this case, the effectors look like the stars in our social graph because they are proficient in the required skill, and many authors have connections with them. Meanwhile, we can trust on these people more than others for the competent support of the project.

3.3.4. JaccardPearson skill grading

We believe that the skill grading model for experts in a social network should not only rely on their skill profiles. Indeed, the main idea of our method is to present a formulation which considers both the expert skill information and his abilities of team working in a collaborative network. We focus on two well-known traditional similarity metrics (Pearson correlation and Jaccard similarity) that have been attracted by extensive researchs on Recommender Systems community (see [7,12,18,25,31]). Pearson correlation corresponds to the Cosine deviation of the mean and considers only the attributes in the common. On the other hand, Jaccard similarity measures the overlap that every two individuals share with their attributes. However, it does not take into account the different usages of rating scale by different users. In our proposed JaccardPearson skill grading, these two traditional measures are combined with simple multiple function to use the benefit of their advantages. This combined measure comprises between 0 and 1. In this adapted formulization, for determining the skillfulness level of each author $v_{i}$ per each skill $s_{k}$ , the similarity between the mentioned author and each of his neighbors $v_{j} \in N_{i}$ , is calculated as follow: $\begin{array}{rclr} Skill - Grading (v_{i}, s_{k}) \\ = \sum_{v_{j} \in N_{i}} {(\frac{| P_{i}^{s_{k}} \cap P_{j}^{s_{k}} |}{| P_{i}^{s_{k}} \cup P_{j}^{s_{k}} |}) \\ \times | | P_{i}^{s_{k}} | - {\bar{P}}_{i} | \times | | P_{j}^{s_{k}} | - {\bar{P}}_{j} |} \\ / ((\sum_{v_{j} \in N_{i}} {(| P_{i}^{s_{k}} | - {\bar{P}}_{i})}^{2}) \\ \times (\sum_{v_{j} \in N_{i}} {(| P_{j}^{s_{k}} | - {\bar{P}}_{j})}^{2}))^{- \frac{1}{2}}, & (14) \\ {\bar{P}}_{i} = \frac{\sum_{s \in S_{v_{i}}} | P_{i}^{s} |}{| S_{v_{i}} |} . & (15) \end{array}$

It is noted that these formulations, including vertices proficiency similarities, vertex similarities and the above skill grading, are implemented offline as a preprocessing phase in our settings.

3.3.5. Cost function

In the present study, the diameter is investigated as a criterion to measure the effectiveness of the selected team. The diameter definition refers to the largest shortest path between any pair of nodes in the graph. By considering the Dijkstra’s algorithm as a method to compute the distance among nodes, the diameter computation only relies on the physical distance. Since effectiveness of the team is a relatively general term, we could generalize its meaning by redefining the magnitude of the diameter as an instantiation of the communication cost. Unlike Lappas et al., we tend to optimize the diameter as a measure of both distance and skillfulness level of team members regards to their ability of contribution. Hence, according to this modification, a new definition of communication cost is presented. The cost of a path which is followed by individual $v_{i}$ to $v_{j}$ for covering the required skill $s_{k}$ is composed of two components: the first one includes the measurable distance between $v_{i}$ and $v_{j}$ , and the other one defines the skilled level of $v_{j}$ regarding to skill $s_{k}$ . These two contributed components of the cost optimization determine the importance and effectiveness of team members based on this improvement. A balanced parameter, ϵ, is used to control the importance of each of the skillfulness and distance components of individual $v_{j}$ . It can be formulated as: $\begin{array}{rclr} Cost {(v_{i}, v_{j})}_{s_{k}} \\ = [ϵ \times \frac{(1 - d (v_{i}, v_{j}))}{num}] \\ \times [(1 - ϵ) \\ \times (1 - Skill - Grading (v_{j}, s_{k}))] . & (16) \end{array}$

Where the parameter $d (v_{i}, v_{j})$ is calculated by using the Dijkstra’s shortest path along $v_{i}$ and $v_{j}$ . The $num$ is the number of nodes along their shortest path while it is used to normalize the cost value. Also, the balanced ϵ is set to 0.5 in our experiments. We apply this cost definition in our Generalized Diameter algorithm instead of using $d (v_{i}, v_{j})$ and everywhere the distance calculation is needed.

Based on the related surveys on the deficiencies of the Pearson correlation [1,36], we trust on SOI and COS more than the skill grading of JaccardPearson similarity measure. Also, corresponding example mentioned afterwards in Section 4.2 verifies this shortage. So, if we want to use the proficiency similarity in the combined cost function, the JaccardPearson skill grading is not appropriate to integrate with other implicit vertex similarities. Despite of its deficiencies, this similarity could be used separately in the aforementioned cost function due to consider both skillfulness level of expert and its ability of contribution. Moreover, JaccardPearson skill grading somehow states the combined concept of our vertex and proficiency similarities. In addition, the algorithm can use the cost function to compare experts based on their minimum diameter distance, implicit vertex similarity or proficiency similarity functions. Then, the algorithm chooses one path to go ahead on searching process and finally gives us the appropriate team.

So, we define new cost function as follows: $\begin{array}{rclr} Cost {(v_{i}, v_{j})}_{s_{k}} \\ = [γ \times \frac{(1 - d (v_{i}, v_{j}))}{num}] \\ + [α \times (1 - Implicit Vertex sim)] \\ + [β \times (1 - Proficiency sim)] . & (17) \end{array}$

Above parameters are balanced by the project manager. If he just evaluates based on diameter distance, γ should be one, and β and α are zero. On the other side, if he just evaluates upon quantity of co-neighbors, α should be one, and β and γ are defined zero. Finally, if these three factors are simultaneously evaluated, the compromising must be done. The balanced γ is set to 0.5 and $α = β = 0.25$ in our experiments which combine all of these measures. Here, our first preference similarity function is based on the quantity of co-authored paper because co-authored DBLP network is evaluated. Furthermore, we can apply the implicit vertex similarities (RSSmax, RSSsigma) separately to prepare a good framework for recommending collaborators by suggesting $γ = 0$ . However, using this implicit vertex similarity does not interfere with the concept of applying co-authored papers as our first preference in the cost function. Actually, as it is mentioned before, the RSS approach is based on the measure of papers that two authors co-author directly or indirectly. The main reason of this suggestion is that when just the implicit vertex similarity measure is used, the intermediates are released in a selection process. Therefore, they are disappeared in the next team generations and consequently in the last determined team. In conclusion, our contribution is trying to pick out just important effectors of social graph for completing the required task. However, this kind of searching is faster than the explicit vertices connections because effectors can find each other without their common neighbors. So, the accomplishing of the project by expert effectors and recommending these effectors to each other for cooperating in the future are the main object of this virtual connected team. Thus, an effective generation of the co-authorship social network could be constructed.

4. Experimental evaluation

4.1. Data set

Finding datasets that reflect the application scenarios of the team formation is the main challenge of current study. In fact, such systems are not widely used, and most data from them is not publicly available. For our experiments, we use the DBLP dataset as a benchmark dataset which is publicly available from the DBLP portal. The snapshot of this dataset was taken on April 12, 2006, while the data is related to papers which are published in areas of Database (DB), Data mining (DM), Artificial intelligence (AI), and Theory (T) conferences. They are used in order to cover the diverse fields of study (including 19 venues as follows: {SIGMODE, VLDB, ICDE, ICDT, EDBT, PODS, WWW, KDD, SDM, PKDD, ICDM, ICML, ECML, COLT, UAI, SODA, FOCS, STOC and STACS}).

The expert social network is constructed by using co-authorship graph in the following procedure. First, to collect the experts, the authors who have less than three papers in DBLP are discarded. This initial purification on dataset removes many authors who are not enough qualified for the selection. Moreover, these authors severely increase cost and cardinality of the team and negatively influence on quality of selections. Then, the skill set $S_{v_{i}}$ of each author $v_{i}$ is filled with the terms that appear in at least two titles of their papers in the co-authorship graph. For the skill extraction, the terms extracted from ‘Bibsonomy’4

⁴
http://www.kde.cs.uni-kassel.de/bibsonomy/dumps.

tag tool are used to avoid noisy tags. Two authors are called connected if they co-authored in at least two papers.

The graph distance between two nodes in the graph $G_{dblp}$ is computed by using the shortest path distance. In this graph, the total number of authors is 5508 where there are 1792 distinct skills and 5588 edges.

The preliminaries for performing our method are as follows. Each task $T = (p, q)$ is characterized by two parameters: (1) p, the number of required skills in a task T; (2) q, the minimum required number of experts to accomplish each skills of T. Specifically, a task T is generated as follows: first, p skills are picked randomly from the terms appearing in published papers. In all experiments reported in this section, we use $p \in {2, 4, \dots, 20}$ and $q = 1$ . Then, for every $(p, q)$ configuration, we generate 100 random tasks for all of the algorithms and take the average performance achieved by different methods.

4.2. Quantitative results

In this section, our results are compared with the well-known algorithm, RarestFirst (Lappas et al.). The influences of proposed similarity measures and their combinations on the cost function to search for suitable teammates are also analyzed. The comparisons are done with respect to the communication cost, team cardinality, the number of disconnected teams and the time complexity under consideration of different similarity measures.

Fig. 4.

Average communication cost, cardinality and number of disconnected team reported by RarestFirst algorithms: (a) Average communication cost. (b) Average cardinality. (c) Average number of disconnected teams. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/AIC-140628.)

Fig. 5.

Average communication cost and cardinality of teams reported by Generalized Diameter algorithms: (a) Average communication cost. (b) Average cardinality. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/AIC-140628.)

The average communication cost, team cardinality and the number of disconnected teams of the Diameter algorithm based on different similarity measures for each specified task are depicted in Figs 4 and 5. Figure 4 shows the efficiencies of similarity measures by RarestFirst Diameter algorithm, and Fig. 5 illustrates them with Generalized Diameter algorithm. The following results are achieved from the analysis of these figures. As we can see in Fig. 4(a) and Fig. 5(a), by increasing the number of required skills, the communication costs of the algorithms grow considerably. It is because the search space which is needed to be explored will be expanded in this case. In the other words, the probability of the existence of experts who are capable to do the required skills decreases due to the sparsity of the underlying graph. Therefore, the size of the team is clearly growing by increasing the number of required skills in Fig. 4(b) and Fig. 5(b).

In the case of similarity measures, Fig. 4(a) and Fig. 5(a) show that the Cosine similarity is less dominated than Jaccard similarity which Lappas et al. used in their cost function. Besides, the VicinityJaccard, VicinityCosine and TopologyOverlap similarity measures present relatively equal results. However, VicinityCosine is somehow better than VicinityJaccard similarity. This result is reasonable in many studies (like [16]) and hence, VicinityCosine is more reliable than VicinityJaccard in the practice. Regarding the relation strength similarity, the outcome of RSSmax is relatively identical to Jaccard similarity, and RSSsigma is partly the same as other three implicit vertex similarities. It is due to the fact that RSSmax selects the largest path and benefits only from one path of the expert’s contribution. While RSSsigma uses the advantages of collaboration abilities of all neighbors, it determines much more effective team than RSSmax. Hence, like Chen et al. [9], the sigma version of RSS is recommended for using relation strength similarity.

The observations from the analysis of Fig. 4(b) and Fig. 5(b) show the comparisons of teams cardinality measures. The algorithm with different similarity measures has been developed regarding the growth of required skills. However, the proposed similarity measures such as VicinityJaccard, VicinityCosine, TopologyOverlap and RSSsigma outperform those other similarities. Hence, they can control the size of the team much better.

According to the implicit vertex similarity measures like RSS, it should be considered that when a degree of separation is increased, the results can be much more effective. Furthermore, the presented framework is general and could be easily extended to be used in higher degrees. Actually, the final selected team would be more efficient by ascending the degree of separation. In this case, the teammate selection is directly formed by the author in the network, and more effectively indirect collaborators are founded. Hence, the algorithm searches for effectors in the whole picture of the social graph. Also, it may be developed in the next snapshot because of introducing effectors for co-authoring in the next generation. So, the communication cost and size of the selected team will become small as much as possible. Although this concept means that a current expert can explore more potential collaborations by degree $n - 1$ on RSS, the complexity of computations limits this chance. In fact, the influence of using the implicit vertext similarity rather than diameter measure is important for us. Hence, just a minimum degree of separation is applied in the presented experiments to show its effects.

Our final evaluation is about the number of disconnected teams. In the real world projects, the employees who are in the same department can communicate and collaborate more easily than other employees who are in the outside. Therefore, it is so importance to detect connected teams to minimize the communication cost. As it is depicted in Fig. 4(c), the Diameter algorithm by various similarity measures like Jaccard similarity first try to find the connected teams. Then, if these teams are not available, they determine the disconnected ones.

As we can see in Fig. 5, compared to RarestFirst algorithm, Generalized Diameter algorithm generally achieves a dramatic decrease in the size of selected team and communication cost. As a matter of fact, in the Generalized Diameter algorithm, for covering each skill, the organized team is checked whether the visited individuals satisfy other required skills or not. This improvement leads to a remarkable reduction in the size of the team and its communication cost. Since the size of selected team could play crucial role in the expense of the project, it has been included and compared with our experimental evaluations. Furthermore, the number of disconnected teams is the same as the RarestFirst algorithm. Hence, the experimental results based on the number of disconnected teams are not depicted again.

Fig. 6.

Average communication cost and cardinality of teams reported by Generalized Diameter algorithms with combination of Cosine for diameter cost, RSS for implicit vertext and SOI, COS for proficiency similarity measure by considering $ϵ = γ = 0.5$ and $α = β = 0.25$ : (a) Average communication cost. (b) Average cardinality. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/AIC-140628.)

According to combination of similarities, Fig. 6 shows that using the proposed similarities and their combinations are satisfied in the cost function. In this experiment, the Cosine similarity is considered for a diameter cost between authors due to approximately better results than Jaccard similarity measure shown in Fig. 4 and Fig. 5. Moreover, RSS is appointed as a representative of the implicit vertex similarity because it can be improved by increasing the degree of separation (hole size) in practice. Hence, we believe that this implicit vertex similarity participating in the comparing process is more appropriate.

As it is mentioned in Section 3.3.5, for combined scenario, the constants are defined as $ϵ = γ = 0.5$ and $α = β = 0.25$ . By raising α (up to $α = 1$ ; RSSsigma), the collaborative recommendation concept will be increased in the framework of effective expert team. Then, finding the suitable team will be proceed faster. In the case of combined proficiency similarities, the results show their effectiveness. It means that the algorithm tries to find the authors who are more expert in the required skill than others corresponding to his skill set.

Fig. 7.

Network of connections between individuals in ${v_{A}, v_{B}, v_{C}, v_{D}, v_{E}, v_{F}}$ .

Although the JaccardPearson skill grading helps the algorithm defining the effective team, the approach has many deficiencies. There are many studies indicating that the Pearson correlation is problematic [1,36]. The following example proves this claim. Suppose we have the weighted graph shown in Fig. 7: In Fig. 7(a), with respect to author $v_{A}$ and $v_{B}$ , the skills frequencies are as follows: $v_{A} = v_{B} = {s_{1} = 10 %, s_{2} = 20 %, s_{3} = 30 %, s_{4} = 40 %}$ . In this case, the Pearson correlation correctly indicates 1. On the other hand, $v_{A}$ and $v_{C}$ are considered as follow: $v_{C} = {s_{1} = 22 %, s_{2} = 24 %, s_{3} = 26 %, s_{4} = 28 %}$ . Although there are some similarities between $v_{A}$ and $v_{C}$ , they are not totally similar as Pearson correlation computes. The other reversal example is between $v_{A}$ and $v_{D}$ while $v_{D} = {s_{1} = 40 %, s_{2} = 30 %, s_{3} = 20 %, s_{4} = 10 %}$ . The Pearson correlation has a value $- 1$ . It means that there is not any similarity between these authors, but the real SOI frequencies show us that the similarity between them is as low as possible. By comparing the last two examples in Fig. 7(b), the Pearson correlation shows authors $v_{E}$ and $v_{F}$ have a similar value equal to $- 0.6$ while the real skills frequency marks that they have no similarities at all. So, we believe that the Pearson correlation is unsatisfactory and shows some flaws. Although the JaccardPearson skill grading shows fine efficiencies in results, the effectiveness of this approach is less than other vertex and proficiency similarities.

Fig. 8.

The efficiency evaluation of using different similarity measures on the Generalized Diameter algorithm for the supposed graph. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/AIC-140628.)

Figure 8 indicates the efficient evaluation of various similarity measures which are used in the Generalized Diameter algorithm on DBLP dataset. We find the followings: first, as seen in Fig. 8, the results show that all of the algorithms associated with RSS similarity measure outperform the other algorithms. The average running time of Diameter algorithm by using RSS, VicinityJaccard and VicinityCosine similarities have gradually increased by rising the number of required skills. The RSS method which provides effectiveness and scalability of the results reduces the search space into a well-condensed form of main effectors. Also, the Diameter algorithm using RSS provides a significant improvement in term of efficiency compared with explicit vertex similarity. The main reason is that when we use approaches like implicit vertex similarities, the intermediates are released in a searching process. In addition, if two authors need to join to each other for making the other searching generation, they can do it at first. Furthermore, these implicit vertex similarities can be used to find more effective team of experts in social graph. They are chosen based on their expertise profiles and their effective contributions in spite of their direct co-authors collaborators. Thus, these implicit co-authors can be suggested to each other to achieve more effective teams in the future.

In summary, it can be seen that more appropriate team of experts can be achieved by using our Generalized Diameter based on proposed similarity measures. The analysis of the experimental results imply that our proposed framework is a selective method by offering promising performance on communication cost and team cardinality of the selected team for the required given task.

5. Conclusion and future work

In the present paper, the problem of finding the effective team of experts which can accomplish a specific given task with minimum communication cost is studied. The proposed framework is formed under different similarity measures. We attribute the team formation problem as a vertices similarity environment based on their common neighbors. Actually, they regard their co-authored paper and their implicit similarities with respect to releasing their intermediates. Moreover, the implicit vertex similarities propose a collaborative recommendation that is based on the team formation framework. They can also identify effectors in social networks established by the structural equivalence relation. Thus, they make the algorithm faster on searching for members of the team. The proficiency similarities are also studied to be involved in the searching process. This measure analyzes the potential expertise of authors according to the measure of interest and contribution of the required task in the social scenario. Although the combination of similarity measures in the cost function causes the algorithm to have more complexity, they help the algorithm to search for the more effective team specially in equal situations. While the implicit vertex similarities are used, applying the maximum degree of separation to search for the suitable collaborators is not feasible due to the very large strategy space. In fact, the influence of using the implicit vertext similarity rather than diameter measure is important for us. Hence, just a minimum degree of separation is applied in presented experiments to show its effect. However, the framework could be easily extended to be used in higher degrees. In addition, it is obvious that the final selected team would be more efficient by rising the degree of separation.

The experimental results on DBLP show that the effective teams could be found with the minimum communication cost, cardinality and number of disconnected teams. Also, the time complexity of using different similarity measures is studied for efficiency estimation of the approach.

For the future works, more constraint teams can be considered. Furthermore, the generalized tasks can be studied and defined with the required skills which should be supported by the minimum number of experts.

Footnotes

Acknowledgement

This work is supported by Iranian Telecommunication Research Center (ITRC) under Grant No. T/500/13226.

References

[1]

Ahlgren,

Jarvening and

Rousseau, Requirements for a cocitation similarity measure, with special reference to Pearsonś correlation coefficient, Journal of the American Society for Information Science and Technology 54(6) (2003), 550–560.

[2]

Anagnostopoulos,

Becchetti and

Castillo, Power in unity: Forming teams in large-scale community systems, in: CIKM’10, 2010.

[3]

Backstrom,

D.P.

Huttenlocher,

J.M.

Kleinberg and

Lan, Group formation in large social networks: Membership, growth and evolution, in: Proc. the ACM Intl. Conference on Knowledge Discovery and Data Mining KDD, 2006, pp. 44–54.

[4]

A.L.

Barabási and

Albert, Emergence of scaling in random networks, Science 286 (1999), 509–512.

[5]

Baykasoglu,

Dereli and

Das, Project team selection using fuzzy optimization approach, Journal of Cybernetics and Systems 38 (2007), 155–185.

[6]

Boon and

Siersksma, Team formation: Matching quality supply and quality demand, European Journal of Operational Research 148 (2003), 277–292.

[7]

Candillier,

Meyer and

Fessant, Designing specific weighted similarity measures to improve collaborative filtering systems, in: Proc. the IEEE Intl. Conference on Data Mining ICDM, 2008, pp. 242–255.

[8]

Cheatham and

Cleereman, Application of social network analysis to collaborative team formation, in: Proc. the Intl. Symposium on Collaborative Technologies and Systems, 2006, pp. 306–311.

[9]

H.-H.

Chen,

Gou,

Zhang and

C.L.

Giles, CollabSeer: A search engine for collaboration discovery, in: JCDL’11, 2011, pp. 231–240.

10.

[10]

S.J.

Chen and

Lin, Modeling team member characteristics for the formation of a multifunctional team in concurrent engineering, IEEE Transactions on Engineering Management 51 (2004), 111–124.

11.

[11]

Dereli,

Baykasoglu and

Sena Das, Fuzzy quality-team formation for value added auditing: A case study, Journal of Engineering and Technology Management 24 (2007), 366–394.

12.

[12]

Deshpande and

Karypis, Item based top-N recommendation algorithms, ACM Transactions on Information Systems 22 (2004), 143–177.

13.

[13]

Farhadi,

Sorkhi,

Hashemi and

Hamzeh, An effective expert team formation in social networks based on skill grading, in: ICDM Workshops’11, 2011, pp. 366–372.

14.

[14]

E.L.

Fitzpatrick and

R.G.

Askin, Forming effective worker teams with multi-functional skill requirements, Journal of Computers & Industrial Engineering 48 (2005), 593–608.

15.

[15]

Gaston,

Simmons and

DesJardins, Adapting network structures for efficient team formation, in: Proc. the AAMAS-04 Workshop on Learning and Evolution in Agent-Based Systems, 2004.

16.

[16]

Hamers,

Hemeryck,

Herweyers,

Janssen,

Keters,

Rousseau and

Vanhoutte, Similarity measures in scientometric research: The Jaccard index versus Salton’s cosine formula, Information Processing & Management 25(3) (1989), 315–318.

17.

[17]

Kargar and

Aijun, Discovering top-k teams of experts with/without a leader in social networks, in: CIKM, 2011, pp. 985–994.

18.

[18]

Karypis, Evaluation of item-based top-N recommendation algorithms, in: Proc. the ACM Intl. Conference on Information and Knowledge Management, CIKM, 2001, pp. 247–254.

19.

[19]

Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM) 46(5) (1999), 604–632.

20.

[20]

A.D.

Korwin,

M.F.

Shipley and

Kleyle, Utilizing fuzzy compatibility of skill sets for team selection in multi-phase projects, Journal of Engineering and Technology Management 19 (2002), 307–319.

21.

[21]

Lappas,

Liu and

Terzi, Finding a team of experts in social networks, in: Proc. of ACM Intl. Conference on Knowledge Discovery and Data Mining (KDD’09), 2009, pp. 467–476.

22.

[22]

Leicht,

Holme and

Newman, Vertex similarity in networks, Physical Review E 73(2) (2006), 26120.

23.

[23]

Leskovec,

Huttenlocher and

Kleinberg, Predicting positive and negative links in online social networks, in: WWW’10, 2010.

24.

[24]

Li and

Shan, Team formation for generalized tasks in expertise social networks, in: Proc. the 2nd SocialCom/PASSAT, August 2010, 2010, pp. 9–16.

25.

[25]

Linden,

Smith and

York, Recommendations: Item to item collaborative filtering, IEEE Internet Computing 7 (2003), 76–80.

26.

[26]

M.K.

Malhotra,

Grover and

Desilvio, Reengineering the new product development process: A framework for innovation and flexibility in high technology firms, Omega 24(4) (1996), 425–441.

27.

[27]

Milo,

Shen-Orr,

Itzkovitz,

Kashtan,

Chklovskii and

Alon, Network motifs: Simple building blocks of complex networks, Science 298 (2002), 824–827.

28.

[28]

Nan Liu and

Yang, EigenRank: A ranking-oriented approach to collaborative filtering, in: SIGIR, 2008, pp. 83–90.

29.

[29]

M.E.J.

Newman, The structure and function of complex networks, SIAM Review 45(2) (2003), 167–256.

30.

[30]

Ravasz,

Somera,

Mongru,

Oltvai and

Barabási, Hierarchical organization of modularity in metabolic networks, Science 297(5586) (2002), 1551.

31.

[31]

Resnick,

Iacovou,

Suchak,

Bergstrom and

Riedl, GroupLens: An open architecture for collaborative filtering of net news, in: Proc. the Conference on Computer Supported Cooperative Work, ACM, 1994, pp. 175–186.

32.

[32]

Salas,

T.L.

Dickinson,

S.A.

Converse and

S.I.

Tannenbaum, Toward an understanding of team performance and training, in: Team: Their Training and Performance,

Swezey and

Salas, eds, NJ Ablex, Norwood, 1992.

33.

[33]

Salton, Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer, Addison-Wesley, 1989.

34.

[34]

Sarwar,

Karypis,

Konstan and

Reidl, Item-based collaborative filtering recommendation algorithms, in: Proceedings of the 10th International Conference on World Wide Web, ACM, 2001, pp. 285–295.

35.

[35]

Tan,

Steinbach and

Kumar, Introduction to Data Mining, Addison-Wesley, 2006.

36.

[36]

Van Eck and

Waltman, Appropriate similarity measures for author cocitation analysis, ERIM Report Series Refence No. ERS-091-LIS, 2007.

37.

[37]

J.M.L.

Van Engelen,

D.J.

Kiewiet and

Terlouw, Improving performance of product development teams through managing polarity, International Studies of Management and Organization 31(1) (2001), 46–63.

38.

[38]

Wasserman, Social Network Analysis: Methods and Applications, Cambridge Univ. Press, Cambridge, 1994.

39.

[39]

D.J.

Watts and

S.H.

Strogatz, Collective dynamics of small-world networks, Nature 393(6684) (1998), 440–442.

40.

[40]

Wi,

Oh,

Mun and

Jung, A team formation model based on knowledge and collaboration, Expert Syst. Appl. 36(5) (2009), 9121–9134.

41.

[41]

Xiang,

Neville and

Rogati, Modeling relationship strength in online social networks, in: WWW’10. 2010.

42.

[42]

Zakarian and

Kusiak, Forming teams: An analytical approach, IIE Transactions 31 (2004), 85–97.