research-article

Discovering top-k teams of experts with/without a leader in social networks

Authors:

Mehdi Kargar,

Aijun AnAuthors Info & Claims

CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge management

Pages 985 - 994

https://doi.org/10.1145/2063576.2063718

Published: 24 October 2011 Publication History

Get Access

Abstract

We study the problem of discovering a team of experts from a social network. Given a project whose completion requires a set of skills, our goal is to find a set of experts that together have all of the required skills and also have the minimal communication cost among them. We propose two communication cost functions designed for two types of communication structures. We show that the problem of finding the team of experts that minimizes one of the proposed cost functions is NP-hard. Thus, an approximation algorithm with an approximation ratio of two is designed. We introduce the problem of finding a team of experts with a leader. The leader is responsible for monitoring and coordinating the project, and thus a different communication cost function is used in this problem. To solve this problem, an exact polynomial algorithm is proposed. We show that the total number of teams may be exponential with respect to the number of required skills. Thus, two procedures that produce top-k teams of experts with or without a leader in polynomial delay are proposed. Extensive experiments on real datasets demonstrate the effectiveness and scalability of the proposed methods.

References

[1]

A. Anagnostopoulos, L. Becchetti, C. Castillo, A. Gionis, and S. Leonardi. Power in unity: Forming teams in large-scale community systems. In Proc. of CIKM'10, 2010.

Digital Library

Google Scholar

[2]

E. M. Arkin and R. Hassin. Minimum-diameter covering problems. Networks, 36, 2000.

Google Scholar

[3]

L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In Proc. of KDD'06, 2006.

Digital Library

Google Scholar

[4]

A. Baykasoglu, T. Dereli, and S. Das. Project team selection using fuzzy optimization approach. Cybern. Syst., 38(2):155--185, 2007.

Digital Library

Google Scholar

[5]

E. Fitzpatrick and R. Askin. Forming effective worker teams with multi functional skill requirements. Comput. Ind. Eng., 48(3):593--608, 2005.

Digital Library

Google Scholar

[6]

R. Goldman, N. Shivakumar, S. Venkatasubramanian, and H. Garcia-Molina. Proximity search in databases. In Proc. of VLDB'98, 1998.

Digital Library

Google Scholar

[7]

K. Golenberg, B. Kimelfeld, and Y. Sagiv. Keyword proximity search in complex data graphs. In Proc. of SIGMOD'08, 2008.

Digital Library

Google Scholar

[8]

M. Jackson. Network formation. The New Palgrave Dictionary of Economics and the Law, 2008.

Crossref

Google Scholar

[9]

M. Kargar and A. An. Keyword search in graphs: Finding r-cliques. In Proc. of VLDB'11, 2011.

Digital Library

Google Scholar

[10]

T. Lappas, L. Liu, and E. Terzi. Finding a team of experts in social networks. In Proc. of KDD'09, 2009.

Digital Library

Google Scholar

[11]

E. Lawler. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18, 1972.

Google Scholar

[12]

C. Li and M. Shan. Team formation for generalized tasks in expertise social networks. In Proc. of IEEE International Conference on Social Computing, 2010.

Digital Library

Google Scholar

[13]

L. Qin, J. Yu, L. Chang, and Y. Tao. Querying communities in relational databases. In Proc. of ICDE'09, 2009.

Digital Library

Google Scholar

[14]

H. Wi, S. Oh, J. Mun, and M. Jung. A team formation model based on knowledge and collaboration. Expert Syst. Appl., 36(5):9121--9134, 2009.

Digital Library

Google Scholar

Cited By

View all

Shingade SNiyogi RPichare M(2024)Hybrid Particle Swarm Optimization-Jaya Algorithm for Team FormationAlgorithms10.3390/a1709037917:9(379)Online publication date: 26-Aug-2024
https://doi.org/10.3390/a17090379
Lv BJiang JWu LZhao H(2024)Team formation in large organizations: A deep reinforcement learning approachDecision Support Systems10.1016/j.dss.2024.114343187(114343)Online publication date: Dec-2024
https://doi.org/10.1016/j.dss.2024.114343
Fani HBarzegar RDashti ASaeedi M(2024)A Streaming Approach to Neural Team Formation TrainingAdvances in Information Retrieval10.1007/978-3-031-56027-9_20(325-340)Online publication date: 20-Mar-2024
https://doi.org/10.1007/978-3-031-56027-9_20
Show More Cited By

Index Terms

Discovering top-k teams of experts with/without a leader in social networks
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Retrieving Skill-Based Teams from Collaboration Networks
SIGIR '21: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval

Given a set of required skills, the objective of the team formation problem is to form a team of experts that cover the required skills. Most existing approaches are based on graph methods, such as minimum-cost spanning trees. These approaches, due to ...
Finding a wise group of experts in social networks
ADMA'11: Proceedings of the 7th international conference on Advanced Data Mining and Applications - Volume Part I

Given a task <em>T</em> , a pool of experts <InlineEquation ID="IEq1"><InlineMediaObject><ImageObject Color="BlackWhite" FileRef="978-3-642-25853-4_29_IEq1_HTML.gif" Format="GIF" Rendition="HTML" Type="Linedraw"/></InlineMediaObject> </InlineEquation> ...
Recognizing Experts on Social Media: A Heuristics-Based Approach

Knowing who is an expert on social media is a challenging yet important task, especially in a world where misleading information is commonplace and where social media is an important information source for knowledge seekers. In this paper we investigate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge management

October 2011

2712 pages

ISBN:9781450307178

DOI:10.1145/2063576

Editors:
Bettina Berendt,
Arjen de Vries,
Wenfei Fan,
Craig Macdonald
University of Glasgow, UK
,
Iadh Ounis
University of Glasgow, UK
,
Ian Ruthven
University of Strathclyde, UK

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM '11

Sponsor:

CIKM '11: International Conference on Information and Knowledge Management

October 24 - 28, 2011

Glasgow, Scotland, UK

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

136
Total Citations
View Citations
914
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)7

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shingade SNiyogi RPichare M(2024)Hybrid Particle Swarm Optimization-Jaya Algorithm for Team FormationAlgorithms10.3390/a1709037917:9(379)Online publication date: 26-Aug-2024
https://doi.org/10.3390/a17090379
Lv BJiang JWu LZhao H(2024)Team formation in large organizations: A deep reinforcement learning approachDecision Support Systems10.1016/j.dss.2024.114343187(114343)Online publication date: Dec-2024
https://doi.org/10.1016/j.dss.2024.114343
Fani HBarzegar RDashti ASaeedi M(2024)A Streaming Approach to Neural Team Formation TrainingAdvances in Information Retrieval10.1007/978-3-031-56027-9_20(325-340)Online publication date: 20-Mar-2024
https://doi.org/10.1007/978-3-031-56027-9_20
TÜRKKAHRAMAN ŞKARABULUT K(2023)Sosyal Ağ Varlığında Takım Oluşturma Problemine Hibrit Bir Genetik Algoritma ÖnerisiA Hybrid Genetic Algorithm Proposal for the Team Formation Problem Considering Social NetworkDeu Muhendislik Fakultesi Fen ve Muhendislik10.21205/deufmd.202325731525:73(181-192)Online publication date: 26-Jan-2023
https://doi.org/10.21205/deufmd.2023257315
Hamidi Rad RFani HBagheri EKargar MSrivastava DSzlichta J(2023)A Variational Neural Architecture for Skill-based Team FormationACM Transactions on Information Systems10.1145/358976242:1(1-28)Online publication date: 18-Aug-2023
https://dl.acm.org/doi/10.1145/3589762
Zhang JJiang JWei JZhao H(2023)Prominence convergence in the strategy coordination of crowdsourcing workersFourteenth International Conference on Graphics and Image Processing (ICGIP 2022)10.1117/12.2680526(165)Online publication date: 27-Jun-2023
https://doi.org/10.1117/12.2680526
Addanki BDurga B(2023)Realistic Benchmark Datasets for Team Formation Problem in Social Networks2023 5th International Conference on Recent Advances in Information Technology (RAIT)10.1109/RAIT57693.2023.10127014(1-6)Online publication date: 3-Mar-2023
https://doi.org/10.1109/RAIT57693.2023.10127014
Wang SLi HChu F(2023)A Relax-and-fix Heuristic for Multiple Team Formation Problem2023 IEEE International Conference on Networking, Sensing and Control (ICNSC)10.1109/ICNSC58704.2023.10319045(1-6)Online publication date: 25-Oct-2023
https://doi.org/10.1109/ICNSC58704.2023.10319045
Hamidi Rad RNguyen HAl-Obeidat FBagheri EKargar MSrivastava DSzlichta JZarrinkalam F(2023)Learning heterogeneous subgraph representations for team discoveryInformation Retrieval Journal10.1007/s10791-023-09421-626:1-2Online publication date: 9-Oct-2023
https://doi.org/10.1007/s10791-023-09421-6
Hill APeuker S(2023)Expanding students’ social networks via optimized team assignmentsAnnals of Operations Research10.1007/s10479-023-05492-2332:1-3(1107-1131)Online publication date: 7-Jul-2023
https://doi.org/10.1007/s10479-023-05492-2
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Retrieving Skill-Based Teams from Collaboration Networks

Finding a wise group of experts in social networks

Recognizing Experts on Social Media: A Heuristics-Based Approach