GLaSS: Semi-supervised graph labelling with Markov random walks to absorption
Date
2019
Authors
Glonek, M.
Tuke, S.
Mitchell, L.
Bean, N.
Editors
Aiello, L.M.
Cherifi, C.
Cherifi, H.
Lambiotte, R.
Lio, P.
Rocha, L.M.
Cherifi, C.
Cherifi, H.
Lambiotte, R.
Lio, P.
Rocha, L.M.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Studies in Computational Intelligence, 2019 / Aiello, L.M., Cherifi, C., Cherifi, H., Lambiotte, R., Lio, P., Rocha, L.M. (ed./s), vol.812, pp.304-315
Statement of Responsibility
Max Glonek, Jonathan Tuke, Lewis Mitchell, Nigel Bean
Conference Name
The 7th International Conference on Complex Networks and Their Applications (COMPLEX NETWORKS) (11 Dec 2018 - 13 Dec 2018 : Cambridge, UK)
Abstract
Graph labelling is a key activity of network science, with broad practical applications, and close relations to other network science tasks, such as community detection and clustering. While a large body of work exists on both unsupervised and supervised labelling algorithms, the class of random walk-based supervised algorithms requires further exploration, particularly given their relevance to social and political networks. This work proposes a new semi-supervised graph labelling method, the GLaSS method, that exactly calculates absorption probabilities for random walks on connected graphs, whereas previous methods rely on simulation and approximation. The proposed method models graphs exactly as a discrete time Markov chain, treating labelled nodes as absorbing states. The method is applied to a series of undirected graphs of roll call voting data from the United States House of Representatives. The GLaSS method is compared to existing supervised and unsupervised methods, demonstrating strong and consistent performance when estimating the labels of unlabelled nodes in graphs.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2019 Springer Nature Switzerland AG