Article
Computer Science, Artificial Intelligence
Dongdong Cheng, Qingsheng Zhu, Jinlong Huang, Quanwang Wu, Lijun Yang
Summary: The paper introduces a novel MST-based clustering algorithm LDP-MST, which utilizes local density peaks and a new distance measurement method to effectively discover clusters with complex structures. The experimental results demonstrate that the proposed algorithm is competitive with state-of-the-art methods in cluster discovery.
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
(2021)
Article
Physiology
Jia Li, Jiangwei Li, Chenxu Wang, Fons J. Verbeek, Tanja Schultz, Hui Liu
Summary: This article proposes an adaptive mini-minimum spanning tree-based method, which utilizes a novel distance measure by scaling the Euclidean distance, to detect outliers without prior knowledge of outlier percentages. The results demonstrate the effectiveness of the proposed method compared to state-of-the-art methods.
FRONTIERS IN PHYSIOLOGY
(2023)
Article
Computer Science, Interdisciplinary Applications
Michael Segal, Oren Tzfaty
Summary: The bounded-diameter minimum spanning tree problem seeks to find a minimum weight spanning tree on a connected, weighted, undirected graph G with a diameter no more than D. A new algorithm has been developed that can handle graphs with non-negative weights and has been proven to have a certain performance ratio. The algorithm's performance has been evaluated empirically as well.
COMPUTERS & OPERATIONS RESEARCH
(2022)
Article
Computer Science, Interdisciplinary Applications
Linda Altieri, Daniela Cocchi, Giulia Roli
Summary: This paper reviews the application of entropy measures as standard tools in environmental and ecological sciences to describe data heterogeneity, with a focus on spatial entropy indices and related processing tools. Special attention is given to biodiversity data, and the practical application of these methods to other environmental phenomena is demonstrated. The introduction of the new R package SpatEntropy shows readers how to compute spatial entropy measures in practice, highlighting its unique feature of extending traditional entropy measures to their spatial version.
ENVIRONMENTAL MODELLING & SOFTWARE
(2021)
Article
Computer Science, Interdisciplinary Applications
Cesar Rego, Frank Mathew
Summary: We develop a scatter search algorithm to solve the classical capacitated minimum spanning tree problem, including both homogeneous and heterogeneous variants. This problem is central in network design applications in industrial engineering, routing and logistics, and communication networks. Since it is an NP-Complete problem, heuristic solution methods are necessary to find high-quality solutions within practical time limits. Our proposed algorithm competes with the best algorithms in the literature and avoids complicated artifacts.
ADVANCES IN ENGINEERING SOFTWARE
(2023)
Article
Mathematics
Zhuoran Wang, Dian Ouyang, Yikun Wang, Qi Liang, Zhuo Huang
Summary: Computing directed Minimum Spanning Tree (DMST) is a fundamental problem in graph theory, applied in various fields such as computer network, communication protocol design, revenue maximization in social networks, and syntactic parsing in Natural Language Processing. This paper proposes an indexed approach that reuses computation results for single and batch queries of DMST, achieving significant speedup while consuming minimal index size.
Article
Management
Martine Labbe, Mercedes Landete, Marina Leal
Summary: This study introduces the problem of jointly determining a set of features and a dendrogram according to the single linkage method, proposing different formulations and studying different bounds on the objective function. The effectiveness of the different models is discussed through extensive computational study, comparing the model with valid inequalities to the decomposition algorithm. The computational results also demonstrate that integrating feature selection into the optimization model allows for a satisfactory percentage of information to be preserved.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Computer Science, Interdisciplinary Applications
Alexander V. Smirnov
Summary: This paper mainly studies undirected multiple graphs of any natural multiplicity, including properties of multiple trees and complete spanning trees.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Mathematics
Yoshimi Egawa, Michitaka Furuya, Hajime Matsumura
Summary: In this paper, it is proven that for a sufficiently large integer d and a connected graph G, if the number of vertices in G is less than (d+2)(delta(G)+1)/3, then there exists a spanning tree T of G such that the diameter of T is at most d.
DISCRETE MATHEMATICS
(2021)
Article
Operations Research & Management Science
Francesco Carrabs, Raffaele Cerulli, Rosa Pentangelo, Andrea Raiconi
Summary: The paper presents a branch-and-cut approach to solve the minimum spanning tree problem with conflicting edge pairs, demonstrating its superiority over previous algorithms through computational tests on benchmark instances and newly proposed ones.
ANNALS OF OPERATIONS RESEARCH
(2021)
Article
Energy & Fuels
Nadia Nedjah, Kleber Hochwart Cardoso, Luiza Macedo Mourelle
Summary: This study proposes a distributed implementation of self-healing mechanism in smart grids, which can quickly find satisfactory reconfiguration solutions and enhance network intelligence. The results show that this implementation performs significantly better than the expected upper bounds in terms of reconfiguration time and communication cost, achieving substantial speedup in cases of single and multiple failures.
INTERNATIONAL JOURNAL OF ENERGY RESEARCH
(2021)
Article
Computer Science, Hardware & Architecture
Jose Wagner de Andrade Junior, Rodrigo Duarte Seabra
Summary: This article describes an algorithm that solves a fully dynamic variant of the minimum spanning tree problem. The algorithm achieves an amortized time complexity of O(√n log m) per query by using the square root technique and a data structure called link-cut tree. Instead of using the standard algorithms like Prim or Kruskal, this algorithm takes a different approach to solve the MST problem and improves its complexity with the square root technique. Empirical analysis shows that the proposed algorithm outperforms the standard algorithms, especially when the number of nodes in the graph is large.
Article
Operations Research & Management Science
Pedro Correia, Luis Paquete, Jose Rui Figueira
Summary: This article introduces a new algorithm based on the connectedness property for computing the set of supported non-dominated points and corresponding efficient solutions for the multi-objective spanning tree problem. The algorithm utilizes decomposition of the weight set and adjacency relation in the decision space to determine efficient spanning trees and indifference regions. An in-depth computational analysis is presented for different types of networks with three objectives.
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
(2021)
Article
Mathematics, Interdisciplinary Applications
Jinglian Liu, Daling Wang, Shi Feng, Yifei Zhang
Summary: This paper proposes a two-stage community search algorithm based on node embedding and minimum spanning tree strategy, which maps nodes in a low-dimensional vector space and explores the target community through redefining communities from a distance perspective.
Article
Computer Science, Artificial Intelligence
Manolis N. Kritikos, George Ioannou
Summary: A new variant of the minimum spanning tree problem, referred to as the CMSTP_ATW, is studied with associated time windows and capacities, and a Mixed Integer Programming formulation is devised to model the problem. Experimental results show a strong negative correlation between the GAP of CPLEX and the total number of iterations, indicating potential for improvement. Additionally, a greedy heuristic algorithm is compared to the CPLEX built-in heuristic, showing high quality solutions in short computational times for large-scale test problems.
EXPERT SYSTEMS WITH APPLICATIONS
(2021)
Article
Computer Science, Information Systems
Diansheng Guo, Hai Jin, Peng Gao, Xi Zhu
INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE
(2018)
Article
Computer Science, Information Systems
Caglar Koylu, Diansheng Guo, Yuan Huang, Alice Kasakoff, Jack Grieve
Summary: The study collected and cleaned 92,832 user-contributed family trees with 250 million individuals, creating a population-scale and longitudinal dataset that showed biases in data and high mobility among individuals.
INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE
(2021)
Article
Computer Science, Information Systems
Fengli Xu, Zhen Tu, Hongjia Huang, Shuhao Chang, Funing Sun, Diansheng Guo, Yong Li
Summary: The study suggests that check-in records can be vulnerable to privacy attacks and proposes a new privacy criterion to protect user privacy.
IEEE TRANSACTIONS ON MOBILE COMPUTING
(2021)
Article
Computer Science, Information Systems
Tong Xia, Junjie Lin, Yong Li, Jie Feng, Pan Hui, Funing Sun, Diansheng Guo, Depeng Jin
Summary: The article introduces the 3-Dimensional Graph Convolution Network (3DGCN) framework for predicting citywide crowd flow, achieving superior performance compared to state-of-the-art baselines. By modeling dynamic spatio-temporal graph prediction problems and learning urban structures, the accuracy of predictions is enhanced.
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
(2021)
Article
Computer Science, Information Systems
Jie Feng, Yong Li, Ziqian Lin, Can Rong, Funing Sun, Diansheng Guo, Depeng Jin
Summary: This article proposes a deep learning-based convolutional model, DeepSTN+, for predicting crowd flows in different regions of a city. The model utilizes spatial dependence, time factor, and prior knowledge to improve performance through a stable training process.
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
(2022)
Article
Computer Science, Interdisciplinary Applications
Yingjing Huang, Fan Zhang, Yong Gao, Wei Tu, Fabio Duarte, Carlo Ratti, Diansheng Guo, Yu Liu
Summary: This study proposes a deep learning-based module called Vision-LSTM, which can obtain vector representation from varying numbers of street-level images. The module is validated to effectively recognize urban villages by combining street-level imagery with remote sensing imagery and social sensing data. Compared to existing image fusion methods, Vision-LSTM demonstrates significant effectiveness in capturing associations between street-level images.
COMPUTERS ENVIRONMENT AND URBAN SYSTEMS
(2023)
Proceedings Paper
Computer Science, Artificial Intelligence
Mingyang Zhang, Yong Li, Funing Sun, Diansheng Guo, Pan Hui
Summary: The paper introduces an Adaptive Spatio-Temporal Convolutional Network (ASTCN) to address the spatial and temporal dependencies in traffic prediction. By utilizing a spatial graph learning module and an adaptive temporal convolution module, the ASTCN effectively captures dynamic relationships and complex dependencies in traffic data.
2021 21ST IEEE INTERNATIONAL CONFERENCE ON DATA MINING (ICDM 2021)
(2021)
Proceedings Paper
Computer Science, Artificial Intelligence
Tong Xia, Yunhan Qi, Jie Feng, Fengli Xu, Funing Sun, Diansheng Guo, Yong Li
Summary: The study proposes a novel attentional neural network-based model called AttnMove to densify individual trajectories in sparse mobility data. By designing intra and inter-trajectory attention mechanisms, the model can better capture user mobility regularity and fully utilize periodic patterns from long-term history.
THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE
(2021)
Proceedings Paper
Computer Science, Information Systems
Kai Zhao, Jie Feng, Zhao Xu, Tong Xia, Lin Chen, Funing Sun, Diansheng Guo, Depeng Jin, Yong Li
27TH ACM SIGSPATIAL INTERNATIONAL CONFERENCE ON ADVANCES IN GEOGRAPHIC INFORMATION SYSTEMS (ACM SIGSPATIAL GIS 2019)
(2019)
Article
Computer Science, Interdisciplinary Applications
Xi Zhu, Diansheng Guo, Caglar Koylu, Chongcheng Chen
COMPUTERS ENVIRONMENT AND URBAN SYSTEMS
(2019)
Proceedings Paper
Computer Science, Theory & Methods
Tong Xia, Yue Yu, Fengli Xu, Funing Sun, Diansheng Guo, Depeng Jin, Yong Li
WEB CONFERENCE 2019: PROCEEDINGS OF THE WORLD WIDE WEB CONFERENCE (WWW 2019)
(2019)
Article
Geography
Zhenlong Li, Cuizhen Wang, Christopher T. Emrich, Diansheng Guo
CARTOGRAPHY AND GEOGRAPHIC INFORMATION SCIENCE
(2018)
Article
Computer Science, Artificial Intelligence
Jack Grieve, Chris Montgomery, Andrea Nini, Akira Murakami, Diansheng Guo
FRONTIERS IN ARTIFICIAL INTELLIGENCE
(2019)
Article
Linguistics
Jack Grieve, Andrea Nini, Diansheng Guo
JOURNAL OF ENGLISH LINGUISTICS
(2018)
Article
Geography
Peng Gao, Gregory J. Carbone, Junyu Lu, Diansheng Guo
GEOGRAPHICAL ANALYSIS
(2018)