Multi-attribute Based Influence Maximization in Social Networks

Qiufen Ni; Jianxiong Guo; Hongmin W. Du

doi:10.1007/978-3-030-93176-6_21

Multi-attribute Based Influence Maximization in Social Networks

Qiufen Ni
, Jianxiong Guo
, Hongmin W. Du

Guangdong University of Technology
Beijing Normal University at Zhuhai
Rutgers - The State University of New Jersey, New Brunswick

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

Abstract

Viral marketing on social networks is an important application and hot research problem. Most of the related work on viral marketing focuses on the spread of single information, while a product may associate with multi-attribute in real life. Information on multiple attributes of a product propagates in the social networks simultaneously and independently. The attribute information that a user receives will determine whether he would purchase the product or not. We extend the traditional single information influence maximization problem to the Multi-attribute based Influence Maximization Problem (MIMP). We present the Multi-dimensional IC model (MIC model) for the proposed problem. The objective function for MIMP is proved to be non-submodular, then we solve the problem with the Sandwich Algorithm, which can get a max{f(SU)f¯(SU),f̲(SL∗)f(So∗)}(1-1/e) approximation ratio to the optimal solution. Experiments are conducted in two real world datasets to verify the correctness and effectiveness of the proposed algorithm.

Original language	English
Title of host publication	Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings
Editors	Weili Wu, Hongwei Du
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	240-251
Number of pages	12
ISBN (Print)	9783030931759
DOIs	https://doi.org/10.1007/978-3-030-93176-6_21
State	Published - 2021
Externally published	Yes
Event	15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021 - Virtual, Online Duration: Dec 20 2021 → Dec 22 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13153 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021
City	Virtual, Online
Period	12/20/21 → 12/22/21

ASJC Scopus Subject Areas

Theoretical Computer Science
General Computer Science

Keywords

Approximation algorithm
Influence maximization
Multi-attribute information
Social network

Access to Document

10.1007/978-3-030-93176-6_21

Cite this

Ni, Q., Guo, J., & Du, H. W. (2021). Multi-attribute Based Influence Maximization in Social Networks. In W. Wu, & H. Du (Eds.), Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings (pp. 240-251). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13153 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-93176-6_21

Multi-attribute Based Influence Maximization in Social Networks. / Ni, Qiufen; Guo, Jianxiong; Du, Hongmin W.
Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings. ed. / Weili Wu; Hongwei Du. Springer Science and Business Media Deutschland GmbH, 2021. p. 240-251 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13153 LNCS).

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

Ni, Q, Guo, J & Du, HW 2021, Multi-attribute Based Influence Maximization in Social Networks. in W Wu & H Du (eds), Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13153 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 240-251, 15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021, Virtual, Online, 12/20/21. https://doi.org/10.1007/978-3-030-93176-6_21

Ni Q, Guo J, Du HW. Multi-attribute Based Influence Maximization in Social Networks. In Wu W, Du H, editors, Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 240-251. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-93176-6_21

Ni, Qiufen ; Guo, Jianxiong ; Du, Hongmin W. / Multi-attribute Based Influence Maximization in Social Networks. Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings. editor / Weili Wu ; Hongwei Du. Springer Science and Business Media Deutschland GmbH, 2021. pp. 240-251 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{331dc75870be40998421ddfc0c9d21fe,

title = "Multi-attribute Based Influence Maximization in Social Networks",

abstract = "Viral marketing on social networks is an important application and hot research problem. Most of the related work on viral marketing focuses on the spread of single information, while a product may associate with multi-attribute in real life. Information on multiple attributes of a product propagates in the social networks simultaneously and independently. The attribute information that a user receives will determine whether he would purchase the product or not. We extend the traditional single information influence maximization problem to the Multi-attribute based Influence Maximization Problem (MIMP). We present the Multi-dimensional IC model (MIC model) for the proposed problem. The objective function for MIMP is proved to be non-submodular, then we solve the problem with the Sandwich Algorithm, which can get a max\{f(SU)f¯(SU),f̲(SL∗)f(So∗)\}(1-1/e) approximation ratio to the optimal solution. Experiments are conducted in two real world datasets to verify the correctness and effectiveness of the proposed algorithm.",

keywords = "Approximation algorithm, Influence maximization, Multi-attribute information, Social network",

author = "Qiufen Ni and Jianxiong Guo and Du, \{Hongmin W.\}",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021 ; Conference date: 20-12-2021 Through 22-12-2021",

year = "2021",

doi = "10.1007/978-3-030-93176-6\_21",

language = "English",

isbn = "9783030931759",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "240--251",

editor = "Weili Wu and Hongwei Du",

booktitle = "Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings",

}

TY - GEN

T1 - Multi-attribute Based Influence Maximization in Social Networks

AU - Ni, Qiufen

AU - Guo, Jianxiong

AU - Du, Hongmin W.

PY - 2021

Y1 - 2021

N2 - Viral marketing on social networks is an important application and hot research problem. Most of the related work on viral marketing focuses on the spread of single information, while a product may associate with multi-attribute in real life. Information on multiple attributes of a product propagates in the social networks simultaneously and independently. The attribute information that a user receives will determine whether he would purchase the product or not. We extend the traditional single information influence maximization problem to the Multi-attribute based Influence Maximization Problem (MIMP). We present the Multi-dimensional IC model (MIC model) for the proposed problem. The objective function for MIMP is proved to be non-submodular, then we solve the problem with the Sandwich Algorithm, which can get a max{f(SU)f¯(SU),f̲(SL∗)f(So∗)}(1-1/e) approximation ratio to the optimal solution. Experiments are conducted in two real world datasets to verify the correctness and effectiveness of the proposed algorithm.

AB - Viral marketing on social networks is an important application and hot research problem. Most of the related work on viral marketing focuses on the spread of single information, while a product may associate with multi-attribute in real life. Information on multiple attributes of a product propagates in the social networks simultaneously and independently. The attribute information that a user receives will determine whether he would purchase the product or not. We extend the traditional single information influence maximization problem to the Multi-attribute based Influence Maximization Problem (MIMP). We present the Multi-dimensional IC model (MIC model) for the proposed problem. The objective function for MIMP is proved to be non-submodular, then we solve the problem with the Sandwich Algorithm, which can get a max{f(SU)f¯(SU),f̲(SL∗)f(So∗)}(1-1/e) approximation ratio to the optimal solution. Experiments are conducted in two real world datasets to verify the correctness and effectiveness of the proposed algorithm.

KW - Approximation algorithm

KW - Influence maximization

KW - Multi-attribute information

KW - Social network

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

UR - https://www.scopus.com/pages/publications/85122021638#tab=citedBy

U2 - 10.1007/978-3-030-93176-6_21

DO - 10.1007/978-3-030-93176-6_21

M3 - Conference contribution

AN - SCOPUS:85122021638

SN - 9783030931759

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 240

EP - 251

BT - Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings

A2 - Wu, Weili

A2 - Du, Hongwei

PB - Springer Science and Business Media Deutschland GmbH

T2 - 15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021

Y2 - 20 December 2021 through 22 December 2021

ER -