Motif-based spectral clustering of weighted directed networks

被引:0
作者
William G. Underwood
Andrew Elliott
Mihai Cucuringu
机构
[1] Department of Statistics,
[2] University of Oxford,undefined
[3] Department of Operations Research and Financial Engineering,undefined
[4] Princeton University,undefined
[5] The Alan Turing Institute,undefined
[6] British Library,undefined
[7] School of Mathematics and Statistics,undefined
[8] University of Glasgow,undefined
来源
Applied Network Science | / 5卷
关键词
Motif; Spectral clustering; Weighted network; Directed network; Community detection; Graph Laplacian; Bipartite network;
D O I
暂无
中图分类号
学科分类号
摘要
Clustering is an essential technique for network analysis, with applications in a diverse range of fields. Although spectral clustering is a popular and effective method, it fails to consider higher-order structure and can perform poorly on directed networks. One approach is to capture and cluster higher-order structures using motif adjacency matrices. However, current formulations fail to take edge weights into account, and thus are somewhat limited when weight is a key component of the network under study.We address these shortcomings by exploring motif-based weighted spectral clustering methods. We present new and computationally useful matrix formulae for motif adjacency matrices on weighted networks, which can be used to construct efficient algorithms for any anchored or non-anchored motif on three nodes. In a very sparse regime, our proposed method can handle graphs with a million nodes and tens of millions of edges. We further use our framework to construct a motif-based approach for clustering bipartite networks.We provide comprehensive experimental results, demonstrating (i) the scalability of our approach, (ii) advantages of higher-order clustering on synthetic examples, and (iii) the effectiveness of our techniques on a variety of real world data sets; and compare against several techniques from the literature. We conclude that motif-based spectral clustering is a valuable tool for analysis of directed and bipartite weighted networks, which is also scalable and easy to implement.
引用
收藏
相关论文
共 82 条
[1]  
Aicher C(2014)Learning latent block structure in weighted networks J Compl Netw 3 221-248
[2]  
Jacobs AZ(2005)Scale-free networks in cell biology J Cell Sci 118 4947-4957
[3]  
Clauset A(2018)Simplicial closure and higher-order link prediction Proc Natl Acad Sci 115 11221-11230
[4]  
Albert R(1999)Emergence of scaling in random networks Science 286 509-512
[5]  
Benson AR(2016)Higher-order organization of complex networks Science 353 163-166
[6]  
Abebe R(2014)Cluster analysis of weighted bipartite networks: a new copula-based approach PLoS ONE 9 1-12
[7]  
Schaub MT(2005)Laplacians and the Cheeger inequality for directed graphs Ann Comb 9 1-19
[8]  
Jadbabaie A(2016)Sync-rank: Robust ranking, constrained ranking and rank aggregation via eigenvector and SDP synchronization IEEE Trans Netw Sci Eng 3 58-79
[9]  
Kleinberg J(2013)The index-based subgraph matching algorithm (ISMA): Fast subgraph enumeration in large networks using optimized search trees PLoS ONE 8 1-15
[10]  
Barabási A. -L(1972)Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices IBM Techn Discl Bull 15 938-944