Date of Award

Fall 2021

Publication Type



Computer Science

First Advisor

D. Wu

Second Advisor

S. Samet

Third Advisor

H. Wu


Cluster Hire, Clustering, Social Network, Social Network Analysis, Modified weighted structural clustering algorithm




The concept of effective collaboration within a group is immensely used in organizations as a viable means for improving team performance. Any organization or prominent institute, who works with multiple projects needs to hire a group of experts who can complete a set of projects. When hiring a group of experts, numerous considerations must be taken into account. In the Cluster Hire problem, we are given a set of experts, each having a set of skills. Also, we are given a set of projects, each requiring a set of skills. Upon completion of each project, a profit is generated for an organization. Each expert demands a monetary cost (i.e., salary) to provide his/her expertise in projects. The Cluster Hire problem can be solved by hiring a group of experts for a set of projects within the constraints of a budget for hiring and a working capacity of each expert. An extension to this problem is assuming there exists a social network amongst the experts, which contains their past collaboration information. If two experts have collaborated in the past, then they are preferred to be on the same team in the future. The goal of our research is to find a collaborative group of experts who can work effectively together to complete a set of projects. Currently, the solution to the Cluster Hire problem in social networks is achieved using greedy heuristic algorithms and Integer Linear Programming (ILP) approach. Greedy algorithms often generate fast results, but they make locally optimal choices at each step and do not produce global optimal results. The drawbacks of the ILP approach are that it requires a considerable amount of memory for the creation of variables and constraints and also has a very high processing time for large networks. Whereas, Weighted Structural Clustering Algorithm for Networks (WSCAN) has been proved to produce faster results for Team Formation Problem (i.e., hiring a team of experts for a single project), which is a special case of Cluster Hire problem. We are proposing to solve the Cluster Hire problem in social networks using Modified Weighted Structural Clustering Algorithm for Networks (MWSCAN). We run our experiments on a large dataset of 50K experts. ILP is not capable of working with such large networks. Therefore, we will be comparing our results with the greedy heuristic solution. Our findings indicate that the MWSCAN algorithm generates more efficient results in terms of the number of projects completed and profit produced for the given budget compared to the greedy heuristic algorithm to solve the Cluster Hire problem in social networks.