Identifying a Set of Key Members in Social Networks Using SDP-Based Stochastic Search and Integer Programming Algorithms

Wentao Wu (), Wai Kin Victor Chan, Lei Chi () and Zhiguo Gong ()
Additional contact information
Wentao Wu: Department of Industrial and Systems Engineering, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY 12180, USA
Wai Kin Victor Chan: Department of Industrial and Systems Engineering, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY 12180, USA
Lei Chi: EmblemHealth, 55 Water Street, NY 10041, USA
Zhiguo Gong: Department of Computer and Information Science, Faculty of Science and Technology, University of Macau, Macao, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2017, vol. 34, issue 03, 1-22

Abstract: This paper presents two semi-definite programming (SDP) based methods to solve the Key Player Problem (KPP). The KPP is to identify a set of k nodes (i.e., key players) from a social network of size n such that the number of nodes connected to these k nodes is maximized. The KPP has applications in social diffusion and products adoption as it helps maximizing information diffusion and impact. We first formulate the KPP as an integer program (IP) and then convert it into an SDP formulation, which can be solved efficiently and produce a set of high quality candidate solutions. We develop an IP-based algorithm and a stochastic search (greedy) algorithm to find the final solution for the KPP. We compare our algorithms with existing methods in small and large networks with different network structures, including random graph, scale-free network, and community-based scale-free network (CSN). Computational results show that our algorithms are more efficient in solving the KPP in all networks. In addition, we examine how the network structure influences the nodes coverage. It is found that CSNs allow the highest nodes coverage due to their community and scale-free structure.

Keywords: Key player problem; social network analysis; semi-definite programming; greedy algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595917500026
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:34:y:2017:i:03:n:s0217595917500026

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595917500026

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().