Volume 40, Issue 10 e13451
ORIGINAL ARTICLE

Exploiting community and structural hole spanner for influence maximization in social networks

Xiao Li

Corresponding Author

Xiao Li

School of Management, Capital Normal University, Beijing, China

Correspondence

Xiao Li, School of Management, Capital Normal University, 105 West Third Ring Road North, Haidian District, Beijing 100048, China.

Email: [email protected]

Search for more papers by this author
Ziang Chen

Ziang Chen

School of Management, Capital Normal University, Beijing, China

Search for more papers by this author
First published: 19 September 2023
Citations: 1

Abstract

Viral marketing is a frequently used social marketing strategy which aims to promote products on various social media. In order to devise an efficient viral marketing strategy, influence maximization problem is widely studied in social networks. Influence maximization problem tries to find a set of influential users who could influence social users maximally. However, existed influence maximization algorithms could not satisfy the needs of social marketers well. In social networks, community structure is an important feature where social users are closely connected together in groups, and structural hole spanners are those users who bridge different communities. In order to balance the effectiveness and efficiency of viral marketing in social networks, in this paper, we present to exploit the community structure and structural hole spanners in social networks for solving the influence maximization problem. Different to traditional algorithms, we devise a strategy to approximate social influences of social users to find seeds efficiently. In particular, for an internal user inside a community in social networks, we utilize his social influence to members inside this community to approximate his social influence in the whole social network. For a structural hole spanner who bridges multiple communities, we utilize his social influence to members in these communities to approximate his social influence in the whole network. Based on the approximate social influence, information diffusion model and greedy framework, we propose a Community and Structural Hole Spanner based Greedy (CSHS-G) algorithm which devises several influence lists to store social influences of users and fast computation scheme to find seeds. Besides, to further improve the efficiency, we propose a Community and Structural Hole Spanner based Heuristic (CSHS-H) algorithm which approximates social influences of structural hole spanners by utilizing their 2-hops influences. We conduct a comprehensive performance evaluation on the crawled real-world data set. Experimental results show that, compared to all of the baseline algorithms, our proposed algorithms not only have high efficiency, but also could guarantee larger influence spread.

CONFLICT OF INTEREST STATEMENT

The authors declare no conflict of interest.

DATA AVAILABILITY STATEMENT

The data that support the findings of this study are available on request from the corresponding author. The data are not publicly available due to privacy or ethical restrictions.

The full text of this article hosted at iucr.org is unavailable due to technical difficulties.