Abstract
In this paper we consider the problem of directed and walk-specific spread of information in complex social networks. Traditional models tend to explain “explosive” information spreading on social media (e.g., Twitter) – a broadcast or epidemiological kind of model with a focus on the sequence of newly “infected” nodes generated from a source node to multiple targets. However, the process of (single-track) information flow, wherein there is a node-by-node (and not necessarily a newly visited node) trajectory of information transfer is also a common phenomenon. A key example of interest is the sequence of physician visits of a given patient (a referral sequence) in a physician network, wherein the patient is a carrier of information about treatment or disease. With this motivation in mind, we present a Bayesian Personalized Ranking (BPR) model to predict the next node on a walk of a given network navigator using features derived from network analysis. This problem is related to but different from the well-studied problem of link prediction. We apply our model to data from several years of U.S. patient referrals. We present experiments showing that the adoption of network-based features in the BPR framework improves hit-rate and mean percentile rank for next-node prediction.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
“RVU” stands for “relative value units”, a unit of value of medical service. Different procedures are worth different numbers of RVUs.
- 2.
“HRR” stands for “hospital referral region” a geographic area satisfying various medical care criteria [31].
References
An, C., O’Malley, A.J., Rockmore, D.N.: Referral paths in the U.S. physician network. Appl. Netw. Sci. 3(1), 20 (2018)
An, C., O’Malley, A.J., Rockmore, D.N., Stock, C.D.: Analysis of the US patient referral network. Stat. Med. 37(5), 847–866 (2018)
Lu, L., Zhou, T.: Link prediction in complex networks: a survey. Phys. A Stat. Mech. Appl. 390(6), 1150–1170 (2011)
LibenNowell, D., Kleinberg, J.: The linkprediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 58(7), 1019–1031 (2007)
Clauset, A., Moore, C., Newman, M.E.: Hierarchical structure and the prediction of missing links in networks. Nature 453(7191), 98 (2008)
Adamic, L.A., Adar, E.: Friends and neighbors on the web. Soc. Netw. 25(3), 211–230 (2003)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
Lu, Z., Savas, B., Tang, W., Dhillon, I.S.: Supervised link prediction using multiple sources. In: IEEE 10th International Conference on Data Mining. IEEE (2010)
Chen, W., Yuan, Y., Zhang, L.: Scalable influence maximization in social networks under the linear threshold model. In: IEEE 10th International Conference on Data Mining (ICDM). IEEE (2010)
Saito, K., Nakano, R., Kimura, M.: Prediction of information diffusion probabilities for independent cascade model. In: International Conference on Knowledge-Based and Intelligent Information and Engineering Systems. Springer, Berlin (2008)
Bourigault, S., Lamprier, S., Gallinari, P.: Representation learning for information diffusion through social networks: an embedded cascade model. In: Proceedings of the Ninth ACM WSDM Conference. ACM (2016)
Gomez Rodriguez, M., Leskovec, J., Schölkopf, B: Structure and dynamics of information pathways in online media. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. ACM (2013)
Rodriguez, M.G., Balduzzi, D., Schölkopf, B.: Uncovering the temporal dynamics of diffusion networks. arXiv preprint arXiv:1105.0697 (2011)
Guille, A., Hacid, H., Favre, C., Zighed, D.A.: Information diffusion in online social networks: a survey. ACM Sigmod Rec. 42(2), 17–28 (2013)
Milli, L., Rossetti, G., Pedreschi, D., Giannotti, F.: Information diffusion in complex networks: the active/passive conundrum. In: International Workshop on Complex Networks and Their Applications. Springer, Cham (2017)
Joneydi, S., Khansari, M., Kaveh, A.: An opportunistic network approach towards disease spreading. In: International Workshop on Complex Networks and Their Applications. Springer, Cham (2017)
James, C., Pappalardo, L., Sirbu, A., Simini, F.: Prediction of next career moves from scientific profiles. arXiv preprint arXiv:1802.04830 (2018)
Li, L., Jing, H., Tong, H., Yang, J., He, Q., Chen, B.C.: Nemo: next career move prediction with contextual embedding. In: Proceedings of the 26th International Conference on World Wide Web Companion (2017)
Choi, E., et al.: Multi-layer representation learning for medical concepts. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM (2016)
Choi, E., Bahadori, M.T., Schuetz, A., Stewart, W.F., Sun, J.: Doctor AI: predicting clinical events via recurrent neural networks. In: Machine Learning for Healthcare Conference (2016)
Rendle, S., Freudenthaler, C., Gantner, Z., Schmidt-Thieme, L.: BPR: Bayesian personalized ranking from implicit feedback. In: Proceedings of UAI. AUAI Press, pp. 452–461 (2009)
Wang, P., Guo, J., Lan, Y., Xu, J., Wan, S., Cheng, X.: Learning hierarchical representation model for next basket recommendation. In: Proceedings of the 38th International ACM SIGIR Conference. ACM (2015)
Rendle, S., Freudenthaler, C., Schmidt-Thieme, L.: Factorizing personalized Markov chains for next-basket recommendation. In: Proceedings of the 19th International Conference on World Wide Web. ACM (2010)
Leibon, G., Rockmore, D.N.: Orienteering in knowledge spaces: the hyperbolic geometry of wikipedia mathematics. PloS One 8(7), e67508 (2013)
He, R., Kang, W.C., McAuley, J.: Translation-based recommendation. In: Proceedings of the Eleventh ACM Conference on Recommender Systems. ACM (2017)
Pasricha, R., McAuley, J.: Translation-based factorization machines for sequential recommendation. To appear in Proceedings of the Eleventh ACM Conference on Recommender Systems. ACM (2018)
Peixoto, J.L.: A property of well-formulated polynomial regression models. Am. Stat. 44(1), 26–30 (1990)
Rendle, S.: Factorization machines. In: IEEE 10th International Conference on Data Mining. IEEE (2010)
Lorrain, F., White, H.C.: Structural equivalence of individuals in social networks. J. Math. Sociol. 1(1), 49–80 (1971)
Jaccard, P.: Étude comparative de la distribution florale dans une portion des Alpes et des Jura. Bull. Soc. Vaud. Sci. Nat. 37, 547 (1901)
The Dartmouth Atlas of Heath Care. http://www.dartmouthatlas.org/tools/faq/researchmethods.aspx. Accessed May 2018
Hochreiter, S., Schmidhuber, J.: Long short-term memory. Neural Comput. 9(8), 1735–1780 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
An, C., O’Malley, A.J., Rockmore, D.N. (2019). Walk Prediction in Directed Networks. In: Aiello, L., Cherifi, C., Cherifi, H., Lambiotte, R., Lió, P., Rocha, L. (eds) Complex Networks and Their Applications VII. COMPLEX NETWORKS 2018. Studies in Computational Intelligence, vol 812. Springer, Cham. https://doi.org/10.1007/978-3-030-05411-3_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-05411-3_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-05410-6
Online ISBN: 978-3-030-05411-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)