×

Identifying structural hole spanners to maximally block information propagation. (English) Zbl 1456.91107

Summary: An individual can obtain high profits by playing a bridge role among different communities in a social network, thus acquiring more potential resources from the communities or having control over the information transmitted within the network. Such an individual usually is referred to as a structural hole spanner in the network. Existing studies on the identification of important structural hole spanners focused on only whether a person bridges multiple communities without emphasizing the tie strength of that person connecting to his bridged communities. However, a recent study showed that such tie strength heavily affects the profit the person obtains by playing the bridge role. In this study, we aim to identify the most important hole spanners in a large-scale social network who have strong ties with their bridged communities. Accordingly, we first formulate the top-\(k\) structural hole spanner problem to identify \(k\) nodes in the network such that their removals will block the maximum numbers of information propagations within the network. Due to the NP-hardness of the problem, we then propose a novel \((1-\epsilon)\)-approximation algorithm, where \(\epsilon\) is a given constant with \(0<\epsilon <1\). Although the approximate solution provides a guaranteed performance, it takes some time to deliver the solution, which may not be acceptable in practice. Therefore, we devise a fast, yet scalable, heuristic algorithm for the problem. Finally, we evaluate the performance of the proposed algorithms through extensive experiments, using real-world datasets. The experimental results show that the proposed algorithms are very promising. Especially, the found hole spanners block more than 24% of the information propagations compared to existing algorithms.

MSC:

91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bozorgi, A.; Samet, S.; Kwisthout, J.; Wareham, T., Community-based influence maximization in social networks under a competitive linear threshold model, Knowl.-Based Syst., 134, 149-158 (2017)
[2] Budak, C.; Agrawal, D.; Abbadi, A. E., Limiting the spread of misinformation in social networks, Proc. ACM Int. Conf. World Wide Web (WWW), 665-674 (2011)
[3] Burt, R. S., Structural Holes: The Social Structure of Competition (1995), Harvard University Press
[4] Burt, R. S., Structural holes versus network closure as social capital, Soc. Cap. (2001)
[5] Burt, R. S., Structural holes and good ideas, Am. J. Sociol., 110, 2, 349-399 (2004)
[6] Burt, R. S., Secondhand brokerage: evidence on the importance of local structure for managers, bankers, and analysts, Acad. Manag. J., 50, 1, 119-148 (2007)
[7] Burt, R. S., Structural Holes in Virtual Worlds (2017), Oxford University Press
[8] Chang, L.; Zhang, C.; Lin, X.; Qin, L., Scalable top-\(k\) structural diversity search, Proc. IEEE 33rd Int. Conf. Data Eng. (ICDE), 95-98 (2017)
[9] Chen, W.; Lakshmanan, L. V.S.; Castillo, C., Information and Influence Propagation in Social Networks (2013), Morgan & Claypool Publishers
[10] Chen, J.; Yuan, B., Detecting functional modules in the yeast protein-protein interaction network, Bioinformatics, 22, 18, 2283-2290 (2006) · Zbl 1119.83331
[11] Georgiadis, L.; Tarjan, R. E., Finding dominators revisited: extended abstract, Proc. 15th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), 869-878 (2004) · Zbl 1318.68188
[12] Girvan, M.; Newman, M. E., Community structure in social and biological networks, Proc. Nat. Acad. Sci., 99, 12, 7821-7826 (2002) · Zbl 1032.91716
[13] Goh, K. I.; Cusick, M. E.; Valle, D.; Childs, B.; Vidal, M.; Barabási, A. L., The human disease network, Proc. Nat. Acad. Sci., 104, 21, 8685-8690 (2007)
[14] Goyal, S.; Vega-Redondo, F., Structural holes in social networks, J. Econ. Theory, 137, 1, 460-492 (2007) · Zbl 1132.91321
[15] He, X.; Song, G.; Chen, W.; Jiang, Q., Influence blocking maximization in social networks under the competitive linear threshold model, Proc. SIAM Int. Conf. Data Mining, 463-474 (2012)
[16] He, L.; Lu, C.; Ma, J.; Cao, J.; Shen, L.; Yu, P. S., Joint community and structural hole spanner detection via harmonic modularity, Proc. 22nd ACM Int. Conf. Knowl. Discovery Data Mining (SIGKDD), 875-884 (2016)
[17] Katz, E., The two-step flow of communication: an up-to-date report on an hypothesis, Public Opin. Q., 21, 1, 61-78 (1957)
[18] Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, Proc. 9th ACM Int. Conf. Knowl. Discovery Data Mining (SIGKDD), 137-146 (2003)
[19] Kleinberg, J.; Suri, S.; Tardos, E.; Wexler, T., Strategic network formation with structural holes, Proc. 9th ACM Conf. Electron. Commerce, 284-293 (2008)
[20] Ko, Y. Y.; Cho, K. J.; Kim, S. W., Efficient and effective influence maximization in social networks: a hybrid-approach, Inf. Sci., 465, 144-161 (2018) · Zbl 1441.91060
[21] Kumar, S.; Cheng, J.; Leskovec, J., Antisocial behavior on the web: characterization and detection, Proc. 26th ACM Int. Conf. World Wide Web (WWW) Companion, 947-950 (2017)
[22] Li, J.; Wang, X.; Deng, K.; Yang, X.; Sellis, T.; Yu, J. X., Most influential community search over large social networks, Proc. IEEE 33rd Int. Conf. Data Eng. (ICDE), 871-882 (2017)
[23] Lou, T.; Tang, J., Mining structural hole spanners through information diffusion in social networks, Proc. ACM Int. Conf. World Wide Web (WWW), 825-836 (2013)
[24] Marathe, M. V.; Vullikanti, A. K.S., Computational epidemiology, Commun. ACM, 56, 7, 88-96 (2013)
[25] Mitzenmacher, M.; Upfal, E., Probability and Computing: Randomized Algorithms and Probabilistic Analysis (2005), Cambridge University Press · Zbl 1092.60001
[26] Page, L.; Brin, S.; Motwani, R.; Winograd, T., The pagerank citation ranking: bringing order to the web, Tech. Rep. Stanford InfoLab (1999)
[27] Rezvani, M.; Liang, W.; Xu, W.; Liu, C., Identifying top-\(k\) structural hole spanners in large-scale social networks, Proc. 24th ACM Int. Conf. Inform. Knowl. Manag. (CIKM), 263-272 (2015)
[28] Sun, Y.; Qian, C.; Yang, N.; Yu, P. S., Collaborative inference of coexisting information diffusions, Proc. IEEE Int. Conf. Data Mining (ICDM), 1093-1098 (2017)
[29] Tang, J.; Lou, T.; Kleinberg, J., Inferring social ties across heterogeneous networks, Proc. ACM Int. Conf. Web Search Data Mining (WSDM), 743-752 (2012)
[30] Tang, Y.; Shi, Y.; Xiao, X., Influence maximization in near-linear time: a martingale approach, Proc. ACM Int. Conf. Manag. Data (SIGMOD), 1539-1554 (2015)
[31] Tong, H.; Papadimitriou, S.; Faloutsos, C.; Yu, P. S.; Eliassi-Rad, T., Gateway finder in large graphs: problem definitions and fast solutions, Inf. Retr,, 15, 3-4, 391-411 (2012)
[32] Vosoughi, S.; Roy, D.; Aral, S., The spread of true and false news online, Science,, 359, 1146-1151 (2018)
[33] Xu, W.; Liang, W.; Lin, X.; Yu, J. X., Finding top-\(k\) influential users in social networks under the structural diversity model, Inf. Sci., 355-356, 110-126 (2016) · Zbl 1427.68369
[34] Xu, W.; Rezvani, M.; Liang, W.; Yu, J. X.; Liu, C., Efficient algorithms for the identification of top-\(k\) structural hole spanners in large social networks, IEEE Trans. Knowl. Data Eng., 29, 5, 1017-1030 (2017)
[35] Yang, J.; Leskovec, J., Defining and evaluating network communities based on ground-truth, Knowl. Inf. Syst., 42, 181-213 (2015)
[36] Zhang, H.; Alim, M. A.; Li, X.; Thai, M. T.; Nguyen, H. T., Misinformation in online social networks: detect them all with a limited budget, ACM Trans. Inf. Syst., 34, 3 (2016)
[37] Zareie, A.; Sheikhahmadi, A.; Jalili, M., Identification of influential users in social networks based on users’ interest, Inf. Sci., 493, 217-231 (2019) · Zbl 1451.91158
[38] Zhang, Y.; Yu, J. X., Unboundedness and efficiency of truss maintenance in evolving graphs, Proc. ACM SIGMOD/PODS Int. Conf. Manag. Data (2019)
[39] Zheng, Z.; Ye, F.; Li, R. H., Finding weighted \(k\)-truss communities in large networks, Inf. Sci., 417, 344-360 (2017) · Zbl 1444.91180
[40] Zhang, J.; Zhan, Q.; He, L.; Aggarwal, C. C.; Yu, P. S., Trust hole identification in signed networks, Proc. European Conf. Mach. Learning Principles Practice Knowl. Discovery (ECML-PKDD), 697-713 (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.