Structural Influence Maximization in Social Networks

Dong Jing; Ting Liu

doi:10.1109/iThings/GreenCom/CPSCom/SmartData.2019.00186

Structural Influence Maximization in Social Networks

Dong Jing
, Ting Liu

Faculty of Computing

Harbin Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

With the development and widespread of social applications, large social networks has appeared. Influence maximization problem over social networks has become a popular topic and caused lots of research interests. Given a social network with influence weights on edges and an integer k, the goal of influence maximization problem is to find k seed nodes such that activating them leads to the maximum expected number of activated nodes, according to a propagation model. Previous information propagation models do not consider the effects of structural information on influences, but only consider the influences between nodes independently. In this paper, a novel definition of information propagation model is proposed and the related influence maximization problems is studied. Theoretical analysis shows that the problem is NP-complete, heuristic algorithms are proposed to solve the influence maximization problem on the new model. Finally, the experimental results show that the algorithm proposed is efficient and effective.

Original language	English
Title of host publication	Proceedings - 2019 IEEE International Congress on Cybermatics
Subtitle of host publication	12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1088-1095
Number of pages	8
ISBN (Electronic)	9781728129808
DOIs	https://doi.org/10.1109/iThings/GreenCom/CPSCom/SmartData.2019.00186
State	Published - Jul 2019
Event	12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019 - Atlanta, United States Duration: 14 Jul 2019 → 17 Jul 2019

Publication series

Name	Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019

Conference

Conference	12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019
Country/Territory	United States
City	Atlanta
Period	14/07/19 → 17/07/19

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

Heuristic algorithms
Influence maximization
NP-hard
structural influence

Access to Document

10.1109/iThings/GreenCom/CPSCom/SmartData.2019.00186

Cite this

Jing, D., & Liu, T. (2019). Structural Influence Maximization in Social Networks. In Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019 (pp. 1088-1095). Article 8875330 (Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/iThings/GreenCom/CPSCom/SmartData.2019.00186

Jing, Dong ; Liu, Ting. / Structural Influence Maximization in Social Networks. Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 1088-1095 (Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019).

@inproceedings{6738415a9b214024819e4627e75ed360,

title = "Structural Influence Maximization in Social Networks",

abstract = "With the development and widespread of social applications, large social networks has appeared. Influence maximization problem over social networks has become a popular topic and caused lots of research interests. Given a social network with influence weights on edges and an integer k, the goal of influence maximization problem is to find k seed nodes such that activating them leads to the maximum expected number of activated nodes, according to a propagation model. Previous information propagation models do not consider the effects of structural information on influences, but only consider the influences between nodes independently. In this paper, a novel definition of information propagation model is proposed and the related influence maximization problems is studied. Theoretical analysis shows that the problem is NP-complete, heuristic algorithms are proposed to solve the influence maximization problem on the new model. Finally, the experimental results show that the algorithm proposed is efficient and effective.",

keywords = "Heuristic algorithms, Influence maximization, NP-hard, structural influence",

author = "Dong Jing and Ting Liu",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019 ; Conference date: 14-07-2019 Through 17-07-2019",

year = "2019",

month = jul,

doi = "10.1109/iThings/GreenCom/CPSCom/SmartData.2019.00186",

language = "英语",

series = "Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1088--1095",

booktitle = "Proceedings - 2019 IEEE International Congress on Cybermatics",

address = "美国",

}

Jing, D & Liu, T 2019, Structural Influence Maximization in Social Networks. in Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019., 8875330, Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019, Institute of Electrical and Electronics Engineers Inc., pp. 1088-1095, 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019, Atlanta, United States, 14/07/19. https://doi.org/10.1109/iThings/GreenCom/CPSCom/SmartData.2019.00186

Structural Influence Maximization in Social Networks. / Jing, Dong; Liu, Ting.
Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 1088-1095 8875330 (Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Structural Influence Maximization in Social Networks

AU - Jing, Dong

AU - Liu, Ting

PY - 2019/7

Y1 - 2019/7

N2 - With the development and widespread of social applications, large social networks has appeared. Influence maximization problem over social networks has become a popular topic and caused lots of research interests. Given a social network with influence weights on edges and an integer k, the goal of influence maximization problem is to find k seed nodes such that activating them leads to the maximum expected number of activated nodes, according to a propagation model. Previous information propagation models do not consider the effects of structural information on influences, but only consider the influences between nodes independently. In this paper, a novel definition of information propagation model is proposed and the related influence maximization problems is studied. Theoretical analysis shows that the problem is NP-complete, heuristic algorithms are proposed to solve the influence maximization problem on the new model. Finally, the experimental results show that the algorithm proposed is efficient and effective.

AB - With the development and widespread of social applications, large social networks has appeared. Influence maximization problem over social networks has become a popular topic and caused lots of research interests. Given a social network with influence weights on edges and an integer k, the goal of influence maximization problem is to find k seed nodes such that activating them leads to the maximum expected number of activated nodes, according to a propagation model. Previous information propagation models do not consider the effects of structural information on influences, but only consider the influences between nodes independently. In this paper, a novel definition of information propagation model is proposed and the related influence maximization problems is studied. Theoretical analysis shows that the problem is NP-complete, heuristic algorithms are proposed to solve the influence maximization problem on the new model. Finally, the experimental results show that the algorithm proposed is efficient and effective.

KW - Heuristic algorithms

KW - Influence maximization

KW - NP-hard

KW - structural influence

UR - https://www.scopus.com/pages/publications/85074813994

U2 - 10.1109/iThings/GreenCom/CPSCom/SmartData.2019.00186

DO - 10.1109/iThings/GreenCom/CPSCom/SmartData.2019.00186

M3 - 会议稿件

AN - SCOPUS:85074813994

T3 - Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019

SP - 1088

EP - 1095

BT - Proceedings - 2019 IEEE International Congress on Cybermatics

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019

Y2 - 14 July 2019 through 17 July 2019

ER -

Jing D, Liu T. Structural Influence Maximization in Social Networks. In Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 1088-1095. 8875330. (Proceedings - 2019 IEEE International Congress on Cybermatics: 12th IEEE International Conference on Internet of Things, 15th IEEE International Conference on Green Computing and Communications, 12th IEEE International Conference on Cyber, Physical and Social Computing and 5th IEEE International Conference on Smart Data, iThings/GreenCom/CPSCom/SmartData 2019). doi: 10.1109/iThings/GreenCom/CPSCom/SmartData.2019.00186

Structural Influence Maximization in Social Networks

Abstract

Publication series

Conference

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Cite this