Network inference and machine learning
Section outline
-
Network inference and link prediction indices. Network-based node and link clustering, classification and regression.
Lecture handouts:
Lab handouts:
- (xiv) Node classification and link prediction (py, ows, html, log)
Course readings:
- Leicht, E.A., Holme, P. & Newman, M.E.J., Vertex similarity in networks, Phys. Rev. E 73(2), 026120 (2006).
- Liben‐Nowell, D. & Kleinberg, J., The link‐prediction problem for social networks, J. Am. Soc. Inf. Sci. Tec. 58(7), 1019-1031 (2007).
- → Clauset, A., Moore, C. & Newman, M.E.J., Hierarchical structure and the prediction of missing links in networks, Nature 453(7191), 98-101 (2008).
- → Guimera, R. & Sales-Pardo, M., Missing and spurious interactions and the reconstruction of complex networks, P. Natl. Acad. Sci. USA 106(52), 22073-22078 (2009).
- → Godoy-Lorite, A., Guimerà, R. et al., Accurate and scalable social recommendation using stochastic block models,
P. Natl. Acad. Sci. USA 113(50), 14207–14212 (2016).
- Gomez-Rodriguez, M., Leskovec, J. & Krause, A., Inferring networks of diffusion and influence, ACM Trans. Knowl. Discov. Data 5(4), 21:1-37 (2012).
- Zhou, T., Lü, L. & Zhang, Y.-C., Predicting missing links via local information, Eur. Phys. J. B 71(4), 623-630 (2009).
- → Backstrom, L. & Leskovec, J., Supervised random walks, In: Proceedings of WSDM '11 (Hong Kong, China, 2011), pp. 635-644.
- Yan, B. & Gregory, S., Finding missing edges in networks based on their community structure, Phys. Rev. E 85(5), 056112 (2012).
- Wu, Z., Lin, Y. et al., Link prediction with node clustering coefficient, Physica A 452, 1-8 (2016).
- Lü, L. & Zhou, T., Link prediction in complex networks: A survey, Physica A 390(6), 1150-1170 (2011).
- Li, Z., Fang, X. & Sheng, O., A survey of link recommendation for social networks, e-print arXiv:1511.01868v1, pp. 34 (2015).
- Martin, T., Ball, B. & Newman, M.E.J., Structural inference for uncertain networks, Phys. Rev. E 93(1), 012306 (2016).
- Newman, M.E.J., Network structure from rich but noisy data, Nat. Phys. 14, 542-545 (2018).
- Getoor, L. & Diehl, C.P., Link mining: A survey
, SIGKDD Explor. 7(2), 3–12 (2005).
- Getoor, L., Friedman, N. et al., Learning probabilistic models of link structure , J. Mach. Learn. Res. 3, 679–707 (2002).
- Neville, J. & Jensen, D., Iterative classification in relational data , In: Proceedings of SRL ’00 (Austin, TX, USA, 2000), pp. 13–20.
- Macskassy, S.A. & Provost, F., Classification in networked data: A toolkit and a univariate case study , J. Mach. Learn. Res. 8, 935-983 (2007).
- Bhattacharya, I. & Getoor, L., Collective entity resolution in relational data , ACM Trans. Knowl. Discov. Data 1(1), 5:1-9 (2007).
- Bhagat, S., Cormode, G. & Muthukrishnan, S., Node classification in social networks, e-print arXiv:1101.3291v1, pp. 37 (2011).
- McAuley, J.J. & Leskovec, J., Learning to discover social circles in ego networks , In: Proceedings of NIPS ’12 (Lake Tahoe, NV, USA, 2012), pp. 548-556.
- Šubelj, L., Exploratory and predictive tasks of network community detection , In: Proceedings of NetSci '15 (Zaragoza, Spain, 2015), p. 1.
- Hric, D., Peixoto, T.P. & Fortunato, S., Network structure, metadata and the prediction of missing nodes, Phys. Rev. X 6(3), 031038 (2016).
- → Zanin, M., Papo, D. et al., Combining complex networks and data mining: Why and how, Phys. Rep. 635, 1-44 (2016).
- Perozzi, B., Al-Rfou, R. & Skiena, S., DeepWalk, In: Proceedings of KDD ’14 (New York, NY, USA, 2014), pp. 701-710.
- → Grover, A. & Leskovec, J., node2vec, In: Proceedings of KDD ’16 (San Francisco, CA, USA, 2016), pp. 855-864.
- → Figueiredo, D.R., Ribeiro, L.F.R. & Saverese, P.H.P., struc2vec, In: Proceedings of KDD ’17 (Halifax, Canada, 2017), pp. 1–9.
- → Peel, L., Graph-based semi-supervised learning for relational networks, In: Proceedings of SDM ’17 (Houston, TX, USA, 2017), pp. 1-11.
- Hu, W., Fey, M. et al., Open graph benchmark: Datasets for machine learning on graphs, e-print arXiv:1101.3291v1, pp. 23 (2020).