Affiliated with RCfalse
Identifying a Set of Key Members in Social Networks Using SDP-Based Stochastic Search and Integer Programming Algorithms
Wentao Wu1; Wai Kin Victor Chan1; Lei Chi2; Zhiguo Gong3
2017-06-19
Source PublicationASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH
ABS Journal Level1
ISSN0217-5959
Volume34Issue:3
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.

KeywordKey Player Problem Social Network Analysis Semi-definite Programming Greedy Algorithm
DOI10.1142/S0217595917500026
URLView the original
Indexed BySCIE ; SSCI
Language英語English
WOS Research AreaOperations Research & Management Science
WOS SubjectOperations Research & Management Science
WOS IDWOS:000404045900008
PublisherWORLD SCIENTIFIC PUBL CO PTE LTD
The Source to ArticleWOS
Fulltext Access
Citation statistics
Cited Times [WOS]:2   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionDEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Affiliation1.Department of Industrial and Systems Engineering, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY 12180, USA
2.EmblemHealth, 55 Water Street, NY 10041, USA
3.Department of Computer and Information Science, Faculty of Science and Technology, University of Macau, Macao, P. R. China
Recommended Citation
GB/T 7714
Wentao Wu,Wai Kin Victor Chan,Lei Chi,et al. Identifying a Set of Key Members in Social Networks Using SDP-Based Stochastic Search and Integer Programming Algorithms[J]. ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH,2017,34(3).
APA Wentao Wu,Wai Kin Victor Chan,Lei Chi,&Zhiguo Gong.(2017).Identifying a Set of Key Members in Social Networks Using SDP-Based Stochastic Search and Integer Programming Algorithms.ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH,34(3).
MLA Wentao Wu,et al."Identifying a Set of Key Members in Social Networks Using SDP-Based Stochastic Search and Integer Programming Algorithms".ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 34.3(2017).
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Wentao Wu]'s Articles
[Wai Kin Victor Chan]'s Articles
[Lei Chi]'s Articles
Baidu academic
Similar articles in Baidu academic
[Wentao Wu]'s Articles
[Wai Kin Victor Chan]'s Articles
[Lei Chi]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Wentao Wu]'s Articles
[Wai Kin Victor Chan]'s Articles
[Lei Chi]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.