UM  > 科技學院  > 電腦及資訊科學系
Identifying a Set of Key Members in Social Networks Using SDP-Based Stochastic Search and Integer Programming Algorithms
Wu, Wentao1; Chan, Wai Kin Victor1; Chi, Lei2; Gong, Zhiguo3
2017-06
Source PublicationASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH
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 BySCI ; SSCI ; SSCI
Language英语
WOS Research AreaOperations Research & Management Science
WOS SubjectOperations Research & Management Science
WOS IDWOS:000404045900008
PublisherWORLD SCIENTIFIC PUBL CO PTE LTD
The Source to ArticleWOS
全文获取链接
引用统计
被引频次[WOS]:2   [WOS记录]     [WOS相关记录]
Document TypeJournal article
专题DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Affiliation1.Rensselaer Polytech Inst, Dept Ind & Syst Engn, 110 8th St, Troy, NY 12180 USA
2.EmblemHealth, 55 Water St, New York, NY 10041 USA
3.Univ Macau, Fac Sci & Technol, Dept Comp & Informat Sci, Macau, Peoples R China
推荐引用方式
GB/T 7714
Wu, Wentao,Chan, Wai Kin Victor,Chi, Lei,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 Wu, Wentao,Chan, Wai Kin Victor,Chi, Lei,&Gong, Zhiguo.(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 Wu, Wentao,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).
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
Google Scholar
中相似的文章 Google Scholar
[Wu, Wentao]的文章
[Chan, Wai Kin Victor]的文章
[Chi, Lei]的文章
Baidu academic
中相似的文章 Baidu academic
[Wu, Wentao]的文章
[Chan, Wai Kin Victor]的文章
[Chi, Lei]的文章
Bing Scholar
中相似的文章 Bing Scholar
[Wu, Wentao]的文章
[Chan, Wai Kin Victor]的文章
[Chi, Lei]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。