Show simple item record

dc.contributor.authorLi, Huanen
dc.contributor.authorCucuringu, Mihaien
dc.contributor.authorSun, Heen
dc.contributor.authorZanetti, Lucaen
dc.date.accessioned2020-01-28T00:31:37Z
dc.date.available2020-01-28T00:31:37Z
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/301320
dc.description.abstractGraph clustering is a basic technique in machine learning, and has widespread applications in different domains. While spectral techniques have been successfully applied for clustering undirected graphs, the performance of spectral clustering algorithms for directed graphs (digraphs) is not in general satisfactory: these algorithms usually require symmetrising the matrix representing a digraph, and typical objective functions for undirected graph clustering do not capture cluster-structures in which the information given by the direction of the edges is crucial. To overcome these downsides, we propose a spectral clustering algorithm based on a complex-valued matrix representation of digraphs. We analyse its theoretical performance on a Stochastic Block Model for digraphs in which the cluster-structure is given not only by variations in edge densities, but also by the direction of the edges. The significance of our work is highlighted on a data set pertaining to internal migration in the United States: while previous spectral clustering algorithms for digraphs can only reveal that people are more likely to move between counties that are geographically close, our approach is able to cluster together counties with a similar socio-economical profile even when they are geographically distant, and illustrates how people tend to move from rural to more urbanised areas.
dc.rightsAll rights reserved
dc.titleHermitian matrices for clustering directed graphs: insights and applicationsen
dc.typeConference Object
dc.identifier.doi10.17863/CAM.48401
dcterms.dateAccepted2020-01-06en
rioxxterms.versionAM
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2020-01-06en
rioxxterms.typeConference Paper/Proceeding/Abstracten
pubs.funder-project-idECH2020 EUROPEAN RESEARCH COUNCIL (ERC) (679660)
pubs.conference-nameAISTATSen
pubs.conference-start-date2020-06-03en
cam.orpheus.counter58*
rioxxterms.freetoread.startdate2023-01-27


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record