Journal Home > Volume 25 , Issue 2
Tsinghua Science and Technology 2020, 25(2): 161-179 https://doi.org/10.26599/TST.2018.9010126
Open Access | Issue | Published: 02 September 2019

Propagation History Ranking in Social Networks: A Causality-Based Approach

Show Author's Information Zheng Wang,  Chaokun Wang( ),  Xiaojun Ye,  Jisheng Pei,  Bin Li
Department of Computer Science and Technology, University of Science and Technology Beijing, China.
School of Software, Tsinghua University, Beijing 100084, China.
China Information Technology Security Evaluation Center, Beijing 100085, China.
Keywords:
social networks, propagation history ranking, causality, information diffusion
Cite this article:
Wang Z, Wang C, Ye X, et al. Propagation History Ranking in Social Networks: A Causality-Based Approach. Tsinghua Science and Technology, 2020, 25(2): 161-179. https://doi.org/10.26599/TST.2018.9010126
Download citation
EndNote(RIS)
BibTeX

412

Views

24

Downloads

Citations

6

Crossref

N/A

WoS

7

Scopus

2

CSCD

Abstract Full text About this article

Information diffusion is one of the most important issues in social network analysis. Unlike most existing works, which either rely on network topology or node profiles, this study focuses on the diffusion itself, i.e., the recorded propagation histories. These histories are the evidence of diffusion and can be used to explain to users what happened in their networks. However, these histories can quickly grow in size and complexity, limiting their capacity to be intuitively understood. To reduce this information overload, in this paper we present the problem of propagation history ranking. The goal is to rank participant edges/nodes by their contribution to the diffusion. We first discuss and adapt a causal measure, Difference of Causal Effects (DCE), as the ranking criterion. Then, to avoid the complex calculation of DCE, we propose two integrated ranking strategies by adopting two indicators. One is responsibility, which captures the necessity aspect of causal effects. We further give an approximate algorithm, which could guarantee a feasible solution, for this indicator. The other is capability, which captures the sufficiency aspect of causal effects. Finally, promising experimental results are presented to verify the feasibility of the proposed ranking strategies.


menu
Abstract
Full text
Outline
About this article

Propagation History Ranking in Social Networks: A Causality-Based Approach

Show Author's information Zheng Wang, Chaokun Wang( ), Xiaojun Ye, Jisheng Pei, Bin Li
Department of Computer Science and Technology, University of Science and Technology Beijing, China.
School of Software, Tsinghua University, Beijing 100084, China.
China Information Technology Security Evaluation Center, Beijing 100085, China.

Abstract

Information diffusion is one of the most important issues in social network analysis. Unlike most existing works, which either rely on network topology or node profiles, this study focuses on the diffusion itself, i.e., the recorded propagation histories. These histories are the evidence of diffusion and can be used to explain to users what happened in their networks. However, these histories can quickly grow in size and complexity, limiting their capacity to be intuitively understood. To reduce this information overload, in this paper we present the problem of propagation history ranking. The goal is to rank participant edges/nodes by their contribution to the diffusion. We first discuss and adapt a causal measure, Difference of Causal Effects (DCE), as the ranking criterion. Then, to avoid the complex calculation of DCE, we propose two integrated ranking strategies by adopting two indicators. One is responsibility, which captures the necessity aspect of causal effects. We further give an approximate algorithm, which could guarantee a feasible solution, for this indicator. The other is capability, which captures the sufficiency aspect of causal effects. Finally, promising experimental results are presented to verify the feasibility of the proposed ranking strategies.

Keywords: social networks, propagation history ranking, causality, information diffusion

References(57)

[1]
D. Yin and Y. Shen, Location- and relation-based clustering on privacy-preserving social networks, Tsinghua Sci. and Technol.,vol. 23, no. 4, pp. 453–462, 2018.
DOI Google Scholar
[2]
D. Hume, A Treatise of Human Nature. London, UK: John Noon, 1739.
DOI
[3]
F. Chierichetti, S. Lattanzi, and A. Panconesi, Rumor spreading in social networks, in Automata, Languages and Programming, S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. Nikoletseas, and W. Thomas, eds. Springer, 2009, pp. 375–386.
DOI
[4]
J. Kostka, Y. A. Oswald, and R. Wattenhofer, Word of mouth: Rumor dissemination in social networks, in Structural Information and Communication Complexity, A. A. Shvartsman and P. Felber, eds. Springer, 2008, pp. 185–196.
[5]
C. T. Li, S. D. Lin, and M. K. Shan, Finding influential mediators in social networks, in Proc. 20th Int Conf Companion on World Wide Web, Hyderabad, India, 2011, pp. 75–76.
DOI
[6]
D. Shah and T. Zaman, Rumors in a network: Who’s the culprit? IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5163–5181, 2011.
DOI Google Scholar
[7]
L. B. Page and J. E. Perry, Reliability polynomials and link importance in networks, IEEE Trans. Reliab., vol. 43, no. 1, pp. 51–58, 1994.
DOI Google Scholar
[8]
D. R. Shier, Network Reliability and Algebraic Structures. New York, NY, USA: Clarendon Press, 1991.
[9]
K. H. Xu, Y. X. Guo, L. K. Guo, Y. G. Fang, and X. L. Li, Control of photo sharing over online social networks, in Proc. 2014 IEEE Global Communications Conf, Austin, TX, USA, 2014, pp. 704–709.
DOI
[10]
K. A. Harrison and A. H. Smith, Some new species and distribution records of Rhizopogon in North America, Can.J. Bot., vol. 46, no. 7, pp. 881–899, 1968.
DOI Google Scholar
[11]
Y. M. Tan, V. Venkatesh, and X. H. Gu, Resilient self-compressive monitoring for large-scale hosting infrastructures, IEEE Trans. Parallel Distrib. Syst., vol. 24, no. 3, pp. 576–586, 2013.
DOI Google Scholar
[12]
L. Page, S. Brin, R. Motwani, and T. Winograd, The PageRank citation ranking: Bringing order to the web, http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf, 1999.
[13]
R. A. Fisher, Statistical Methods for Research Workers. Genesis Publishing Pvt Ltd, 1925.
[14]
J. Pearl, Causality: Models, Reasoning and Inference. Cambridge, UK: Cambridge University Press, 2000.
[15]
J. Y. Campbell, A. W. C. Lo, and A. C. MacKinlay, The Econometrics of Financial Markets. Princeton, NJ, USA: Princeton University Press, 1997.
DOI
[16]
J. Cheney, Causality and the semantics of provenance, arXiv preprint arXiv: 1004.3241, 2010.
Google Scholar
[17]
I. Hacking, Telepathy: Origins of randomization in experimental design, Isis, vol. 79, no. 3, pp. 427–451, 1988.
DOI Google Scholar
[18]
R. L. Wasserstein, Monte Carlo: Concepts, algorithms, and applications, Technometrics, vol. 39, no. 3, p. 338, 1997.
DOI Google Scholar
[19]
H. Chockler and J. Y. Halpern, Responsibility and blame: A structural-model approach, J. Artif. Intell. Res., vol. 22, pp. 93–115, 2004.
DOI Google Scholar
[20]
T. Eiter and T. Lukasiewicz, Complexity results for structure-based causality, Artif. Intell., vol. 142, no. 1, pp. 53–89, 2002.
DOI Google Scholar
[21]
A. Meliou, W. Gatterbauer, K. F. Moore, and D. Suciu, The complexity of causality and responsibility for query answers and non-answers, Proc. VLDB Endow., vol. 4, no. 1, pp. 34–45, 2010.
DOI Google Scholar
[22]
P. Buneman, S. Khanna, and W. C. Tan, Why and where: A characterization of data provenance, in Proc. 8th Int. Conf. Database Theory, London, UK, 2001, pp. 316–330.
DOI
[23]
I. Altintas, O. Barney, and E. Jaeger-Frank, Provenance collection support in the Kepler scientific workflow system, in Proc. Int. Provenance and Annotation Workshop, Chicago, IL, USA, 2006, pp. 118–132.
DOI
[24]
S. Milgram, The small world problem, Psychol. Today, vol. 2, no. 1, pp. 60–67, 1967.
DOI Google Scholar
[25]
G. Strang, Introduction to Applied Mathematics. Wellesley, MA, USA: Wellesley-Cambridge Press, 1986.
DOI
[26]
V. Chvatal, A greedy heuristic for the set-covering problem, Math. Oper. Res., vol. 4, no. 3, pp. 233–235, 1979.
DOI Google Scholar
[27]
B. Qin, S. Wang, X. F. Zhou, and X. Y. Du, Responsibility analysis for lineages of conjunctive queries with inequalities, IEEE Trans. Knowl. Data Eng., vol. 26, no. 6, pp. 1532–1543, 2014.
DOI Google Scholar
[28]
J. McAuley and J. Leskovec, Learning to discover social circles in ego networks, in Proc. 25th Int. Conf. Neural Information Processing Systems, 2012, pp. 539–547, 2012.
[29]
M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou, Walking in Facebook: A case study of unbiased sampling of OSNs, in Proc. 2010 IEEE INFOCOM, San Diego, CA, USA, 2010, pp. 1–9.
DOI
[30]
M. J. Salganik and D. D. Heckathorn, Sampling and estimation in hidden populations using respondent-driven sampling, Sociol. Methodol., vol. 34, pp. 193–239, 2004.
DOI Google Scholar
[31]
E. M. Voorhees and D. K. Harman, TREC: Experiment and Evaluation in Information Retrieval. Cambridge, MA, USA: MIT Press, 2005.
[32]
K. Järvelin and J. Kekäläinen, IR evaluation methods for retrieving highly relevant documents, in Proc. 23rd Ann. Int. ACM SIGIR Conf. Research and Development in Information Retrieval, Athens, Greece, 2000, pp. 41–48.
DOI
[33]
J. Scott, Social Network Analysis. Thousand Oaks, CA, USA: SAGE Publications Ltd, 2017.
DOI
[34]
Z. Wang, X. J. Ye, C. K. Wang, Y. X. Wu, C. P. Wang, and K. W. Liang, RSDNE: Exploring relaxed similarity and dissimilarity from completely-imbalanced labels for network embedding, in Proc. 32nd AAAI Conf Artificial Intelligence, New Orleans, LA, USA, 2018, pp. 475–482.
[35]
Q. Wang, Z. Wang, and X. J. Ye, Equivalence between line and matrix factorization, arXiv preprint arXiv: 1707.05926, 2017.
Google Scholar
[36]
S. Taylor and P. A. Todd, Understanding information technology usage: A test of competing models, Inf. Syst. Res., vol. 6, no. 2, pp. 144–176, 1995.
DOI Google Scholar
[37]
Z. Wang, C. K. Wang, J. S. Pei, X. J Ye, and P. S. Yu, Causality based propagation history ranking in social networks, in Proc. 25th Int. Joint Conf. Artificial Intelligence, New York, NY, USA, 2016, pp. 3917–3923.
[38]
X. Meng, G. Xu, T. Guo, Y. Yang, W. Shen, and K. Zhao, A novel routing method for social delay-tolerant networks, Tsinghua Sci. and Technol., vol. 24, no. 1, pp. 44–51, 2019.
DOI Google Scholar
[39]
M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse, Identification of influential’ spreaders in complex networks, Nat. Phys., vol. 6, no. 11, pp. 888–893, 2010.
DOI Google Scholar
[40]
Z. Wang, C. K. Wang, J. S. Pei, and X. J Ye, Multiple source detection without knowing the underlying propagation model, in Proc. 31st AAAI Conf. Artificial Intelligence, San Francisco, CA, USA, 2017, pp. 217–223.
[41]
W. Chen, Y. J. Wang, and S. Y. Yang, Efficient influence maximization in social networks, in Proc. 15th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Paris, France, 2009, pp. 199–208.
DOI
[42]
S. Chen, J. Fan, G. L. Li, J. H. Feng, K. L. Tan, and J. H. Tang, Online topic-aware influence maximization, Proc. VLDB Endow., vol. 8, no. 6, pp. 666–677, 2015.
DOI Google Scholar
[43]
J. Kleinberg, Bursty and hierarchical structure in streams, Data Min. Knowl. Discovery, vol. 7, no. 4, pp. 373–397, 2003.
DOI Google Scholar
[44]
M. Cataldi, L. Di Caro, and C. Schifanella, Emerging topic detection on twitter based on temporal and social terms evaluation. in Proc. 10th Int. Workshop on Multimedia Data Mining, Washington, DC, USA, 2010, p. 4.
DOI
[45]
N. T. J. Bailey, The Mathematical Theory of Infectious Diseases and Its Applications. London, UK: Charles Griffin & Company Ltd., 1975.
[46]
S. Bikhchandani, D. Hirshleifer, and I. Welch, A theory of fads, fashion, custom, and cultural change as informational cascades, J. Polit. Econ., vol. 100, no. 5, pp. 992–1026, 1992.
DOI Google Scholar
[47]
D. Lewis, Causation, J. Philos., vol. 70, no. 17, pp. 556–567, 1973.
DOI Google Scholar
[48]
J. Y. Halpern and J. Pearl, Causes and explanations: A structural-model approach. Part I: Causes, Br. J. Philos. Sci., vol. 56, no. 4, pp. 843–887, 2005.
DOI Google Scholar
[49]
C. Freire, W. Gatterbauer, N. Immerman, and A. Meliou, The complexity of resilience and responsibility for self-join-free conjunctive queries, Proc. VLDB Endow., vol. 9, no. 3, pp. 180–191, 2015.
DOI Google Scholar
[50]
B. Qin, S. Wang, and X. Y. Du, Efficient responsibility analysis for query answers, in Proc. 18th Int. Conf. Database Systems for Advanced Applications, Wuhan, China, 2013, pp. 239–253.
DOI
[51]
X. Lian and L. Chen, Causality and responsibility: Probabilistic queries revisited in uncertain databases, in Proc. 22nd ACM Int. Conf. Information & Knowledge Management, San Francisco, CA, USA, 2013, pp. 349–358.
DOI
[52]
S. Kleinberg and G. Hripcsak, A review of causal inference for biomedical informatics, J. Biomed. Inf., vol. 44, no. 6, pp. 1102–1112, 2011.
DOI Google Scholar
[53]
J. Y. Li, L. Liu, and T. D. Le, Practical Approaches to Causal Relationship Exploration. Springer, 2015.
DOI
[54]
G. Salton and M. J. McGill, Introduction to Modern Information Retrieval. New York, NY, USA: McGraw-Hill, 1983.
DOI
[55]
W. B. Frakes and R. Baeza-Yates, Information Retrieval: Data Structures and Algorithms. Englewood Cliffs, NJ, USA: Prentice Hall, 1992.
[56]
J. M. Kleinberg, Authoritative sources in a hyperlinked environment, J. ACM, vol. 46, no. 5, pp. 604–632, 1999.
DOI Google Scholar
[57]
C. J. Colbourn, The Combinatorics of Network Reliability. New York, NY, USA: Oxford University Press, 1987.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 28 May 2018
Revised: 07 September 2018
Accepted: 28 September 2018
Published: 02 September 2019
Issue date: April 2020

Copyright

© The author(s) 2020

Acknowledgements

This work was supported in part by the Fundamental Research Funds for the Central Universities (No. FRF-TP-18-016A1), China Postdoctoral Science Foundation Funded Project (No. 2018M640066), and the National Natural Science Foundation of China (No. 61872207).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return