Node-attributed Spatial Graph Partitioning
Node-attributed Spatial Graph Partitioning
复制标题
节点属性空间图划分
DOI：
10.1145/3397536.3422198
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yang, KwangSoo
中科院分区：
文献类型：
--
作者：
Bereznyi, Daniel;Qutbuddin, Ahmad;Her, YoungGu;Yang, KwangSoo
给定一个空间图和一组节点属性，节点属性空间图分区 (NSGP) 问题将节点属性空间图划分为 k 个同质子图，在满足子图大小约束的同时，最小化总 RMSErank1 和边切割。 RMSErank1 是矩阵与其一阶分解之间的均方根误差。 NSGP 问题对于许多社会应用都很重要，例如识别空间图中的同质社区和检测交通事故中的相互关联模式。这个问题是NP困难的；由于空间图的尺寸很大并且子图必须是同质的，即在节点属性方面相似，因此在计算上具有挑战性。本文提出了一种寻找一组同质子图的新方法，该方法可以在满足大小约束的同时最小化总 RMSErank1 和边缘切割。使用美国人口普查数据集和 HP#6 分水岭网络数据集的实验和案例研究表明，所提出的方法将空间图划分为一组同构子图，并降低了计算成本。
Given a spatial graph and a set of node attributes, the Node-attributed Spatial Graph Partitioning (NSGP) problem partitions a node-attributed spatial graph into k homogeneous sub-graphs that minimize both the total RMSErank1 and edge-cuts while meeting a size constraint on the sub-graphs. RMSErank1 is the Root Mean Square Error between a matrix and its rank-one decomposition. The NSGP problem is important for many societal applications such as identifying homogeneous communities in a spatial graph and detecting interrelated patterns in traffic accidents. This problem is NP-hard; it is computationally challenging because of the large size of spatial graphs and the constraint that the sub-graphs must be homogeneous, i.e. similar in terms of node attributes. This paper proposes a novel approach for finding a set of homogeneous sub-graphs that can minimize both the total RMSErank1 and edge-cuts while meeting the size constraint. Experiments and a case study using U.S. Census datasets and HP#6 watershed network datasets demonstrate that the proposed approach partitions a spatial graph into a set of homogeneous sub-graphs and reduces the computational cost.
数据挖掘简介》，Person Education，2007
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
P. Tan;M. Steinbach;Vipin Kumar
通讯作者：
Vipin Kumar
DOI：
10.1007/978-1-4302-0248-6_11
发表时间：
2019-04
期刊：
Scalable Comput. Pract. Exp.
影响因子：
--
作者：
Chet Langin
通讯作者：
Chet Langin
为水文模型描绘洪泛区和高地地区：方法比较
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
H. Rathjens;K. Bieger;I. Chaubey;J. Arnold;P. Allen;R. Srinivasan;D. Bosch;M. Volk
通讯作者：
M. Volk