检索结果-内蒙古大学图书馆

force-directed algorithms for schematic drawings and placement: A survey

INFORMATION VISUALIZATION 2020年第1期19卷 65-91页

作者： Cheong, Se-Hang Si, Yain-Whar Univ Macau Fac Sci & Technol Dept Comp & Informat Sci Ave Univ Taipa Macao Peoples R China

force-directed algorithms have been developed over the last 50 years and used in many application fields, including information visualisation, biological network visualisation, sensor networks, routing algorithms, scheduling, and graph drawing. Our survey provides a comprehensive summary of developments and a full roadmap for state-of-the-art force-directed algorithms in schematic drawings and placement. We classified the model of force-directed algorithms into classical and hybrid. The classical force-directed algorithms are further classified as follows: (a) accumulated force models, (b) energy function minimisation models and (c) combinatorial optimisation models. The hybrid force-directed algorithms are classified as follows: (a) parallel and hardware accelerated models, (b) multilevel force-directed models and (c) multidimensional scaling force-directed algorithms. Five categories of application domains in which force-directed algorithms have been adopted for schematic drawings and placement are also summarised: (a) aesthetic drawings for general networks, (b) component placement and scheduling in high-level synthesis of very-large-scale integration circuits design, (c) information visualisation, (d) biological network visualisation and (e) node placement and localisation for sensor networks.

关键词： force-directed algorithms schematic drawing force-directed placement information visualisation

来源：评论

学校读者我要写书评

暂无评论

Online force-directed algorithms for visualization of dynamic graphs

引用

INFORMATION SCIENCES 2021年 556卷 223-255页

作者： Cheong, Se-Hang Si, Yain-Whar Wong, Raymond K. Univ Macau Dept Comp & Informat Sci Macau Peoples R China Univ New South Wales Sch Comp Sci & Engn Sydney NSW Australia

force-directed (FD) algorithms can be used to explore relationships in social networks, visualize money markets, and analyze transaction networks. However, FD algorithms are mainly designed for visualizing static graphs in which the topology of the networks remains constant throughout the calculation. In contrast to static graphs, nodes and edges in dynamic graphs can be added or removed as time progresses. In these situations, existing FD algorithms do not scale well, since any changes in the topology will trigger these algorithms to completely restart the entire computation. To alleviate this problem, we propose a design and implementation of five online FD algorithms to visualize dynamic graphs while maintaining their native force models. The online FD algorithms developed in this paper are able to reuse the force models of existing FD algorithms without significant modifications. To evaluate the effectiveness of the proposed approach, online FD algorithms are compared against static FD algorithms for visualizing dynamic graphs. Experimental results show that among the five algorithms evaluated, the online FD algorithm achieves the best number of edge crossings and the standard deviation of edge lengths for visualizing dynamic graphs. (C) 2021 Elsevier Inc. All rights reserved.

关键词： force-directed algorithms Visualization Dynamic graphs Online algorithms

来源：评论

学校读者我要写书评

暂无评论

Snapshot Visualization of Complex Graphs with force-directed algorithms 9

Snapshot Visualization of Complex Graphs with Force-directed...

引用

9th IEEE International Conference on Big Knowledge (ICBK)

作者： Cheong, Se-Hang Si, Yain-Whar Univ Macau Dept Comp & Informat Sci Taipa Macao Peoples R China

ISBN: (纸本)9781538691250

force-directed algorithms are widely used for visualizing graphs. However, these algorithms are computationally expensive in producing good quality layouts for complex graphs. The layout quality is largely influenced by execution time and methods' input parameters especially for large complex graphs. The snapshots of visualization generated from these algorithms are useful in presenting the current view or a past state of an information on timeslices. Therefore, researchers often need to make a trade-off between the quality of visualization and the selection of appropriate force-directed algorithms. In this paper, we evaluate the quality of snapshots generated from 7 force-directed algorithms in terms of number of edge crossing and the standard deviations of edge length. Our experimental results showed that KK, FA2 and DH algorithms cannot produce satisfactory visualizations for large graphs within the time limit. KK-MS-DS algorithm can process large and planar graphs but it does not perform well for graphs with low average degrees. KK-MS algorithm produces better visualizations for sparse and non-clustered graphs than KK-MS-DS algorithm.

关键词： Snapshot visualization Time-constrained execution Complex structured graphs force-directed algorithms

来源：评论

学校读者我要写书评

暂无评论

Performance Comparisons between force-directed algorithms on Structured Data Analysis 7

Performance Comparisons between Force-directed Algorithms on...

引用

7th International Conference on Virtual Reality and Visualization (ICVRV)

作者： Hua, Jie Huang, Mao Lin Wang, Guohua Univ Technol Sydney Sydney NSW Australia South China Univ Technol Guangzhou Guangdong Peoples R China

ISBN: (纸本)9781538626368

Evaluation on the performance of relevant force-directed algorithms is still a challenge, since layout quality is largely relying on personal judgement and/or methods' input parameters, and most aesthetics criteria conflict with each other. This study conducts the performance measurements of four algorithms in terms of seven commonly applied aesthetic criteria and demonstrates the experimental framework.

关键词： Graph drawing force-directed algorithms aesthetic criteria evaluation

来源：评论

学校读者我要写书评

暂无评论

Importance of Numerical Implementation and Clustering Analysis in force-directed algorithms for Accurate Community Detection

引用

APPLIED MATHEMATICS AND COMPUTATION 2022年 431卷

作者： Gouvea, Alessandra M. M. M. Rubido, Nicolas Macau, Elbert E. N. Quiles, Marcos G. Univ Fed Sao Paulo 1201 Av Cesare Monsueto Giulio Lattes BR-12247014 Sao Jose Dos Campos SP Brazil Univ Aberdeen Kings Coll Inst Complex Syst & Math Biol Aberdeen AB24 3UE Scotland Univ Republica Inst Fis Fac Ciencias Igua 4225 Montevideo 11400 Uruguay

Real-world networks show community structures - groups of nodes that are densely intraconnected and sparsely inter-connected to other groups. Nevertheless, Community Detection (CD) is non-trivial, since identifying these groups of nodes according to their local connectivity can hold many plausible solutions, leading to the creation of different methods. In particular, CD has recently been achieved by force-directed algorithms (FDAs), which originally were designed as a way to visualize networks. FDAs map the network nodes as particles in a D-dimensional space that are affected by forces acting in accordance to the connectivity. However, the literature on FDA-based methods for CD has grown in parallel from the classical methods, leaving several open questions, such as how accurately FDAs can recover communities compared to classical methods. In this work, we start to fill these gaps by evaluating different numerical implementations of 5 FDA methods and different clustering analyses on state-of-the-art network benchmarks - including networks with or without weights and networks with a hierarchical organisation. We also compare these results with 8, well-known, classical CD methods. Our findings show that FDA methods can achieve higher accuracy than classical methods, albeit their effectiveness depends on the chosen setting - with optimisation techniques leading over numerical integration and distance-based clustering algorithms leading over density-based ones. Overall, our work provides detailed information for any researcher aiming to apply FDAs for community detection. (C) 2022 Elsevier Inc. All rights reserved.

关键词： Complex Networks Community Detection force-directed algorithms Clustering Analysis

来源：评论

学校读者我要写书评

暂无评论

SubLinearforce: Fully Sublinear-Time force Computation for Large Complex Graph Drawing

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2024年第7期30卷 3386-3399页

作者： Meidiana, Amyra Hong, Seok-Hee Cai, Shijun Torkel, Marnijati Eades, Peter Univ Sydney Sydney NSW 2006 Australia

Recent works in graph visualization attempt to reduce the runtime of repulsion force computation of force-directed algorithms using sampling. However, they fail to reduce the runtime for attraction force computation to sublinear in the number of edges. We present the SubLinearforce framework for a fully sublinear-time force computation algorithm for drawing large complex graphs. More precisely, we present new sublinear-time algorithms for the attraction force computation of force-directed algorithms. We then integrate them with sublinear-time repulsion force computation to give a fully sublinear-time force computation. Extensive experiments show that our algorithms compute layouts on average 80% faster than the existing linear-time force computation algorithm, while obtaining significantly better quality metrics such as edge crossing and shape-based metrics.

关键词： force Runtime Measurement Resistance Approximation algorithms Springs Scalability Graph drawing force-directed algorithms sublinear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A force-directed Approach for Offline GPS Trajectory Map Matching 18

A Force-Directed Approach for Offline GPS Trajectory Map Mat...

引用

26th ACM-SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS)

作者： Rappos, Efstratios Robert, Stephan Cudre-Mauroux, Philippe Univ Appl Sci Western Switzerland HES SO Haute Ecole Ingn & Gest Canton Vaud Yverdon Switzerland Univ Fribourg eXascale Infolab Fribourg Switzerland

ISBN: (纸本)9781450358897

We present a novel algorithm to match GPS trajectories onto maps offline (in batch mode) using techniques borrowed from the field of force-directed graph drawing. We consider a simulated physical system where each GPS trajectory is attracted or repelled by the underlying road network via electrical-like forces. We let the system evolve under the action of these physical forces such that individual trajectories are attracted towards candidate roads to obtain a map matching path. Our approach has several advantages compared to traditional, routing-based, algorithms for map matching, including the ability to account for noise and to avoid large detours due to outliers in the data whilst taking into account the underlying topological restrictions (such as one-way roads). Our empirical evaluation using real GPS traces shows that our method produces better map matching results compared to alternative offline map matching algorithms on average, especially for routes in dense, urban areas.

关键词： Map matching force-directed algorithms GPS trajectory road map offline routing

来源：评论

学校读者我要写书评

暂无评论

Trust Network Visualization Based on force-directed Layout

Trust Network Visualization Based on Force-Directed Layout

引用

10th Web Information System and Application Conference (WISA)

作者： Gan, Zaobin Li, Na Ma, Yao Lu, Hongwei Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Peoples R China

ISBN: (纸本)9780769551340

As a formal description approach, the trust network can intuitively describe trust relationships among entities in virtual communities and attracts great attentions. The trust network visualization is a key to explore the mechanism of trust propagation and study the trust evaluation. Most existing network visualization approaches only take into account the undirected and unweighted graphs, which cannot illustrate the asymmetry and the discreteness of trust relationships. To solve this issue, we define the public influence weight, the trust strength and the trust distance in this paper and propose the force-directed visualization algorithm for trust network. In the visualization algorithm, the desirable length between two nodes is determined by the trust strength so as to cluster trusted entities, and the forces between two different nodes are determined by their public influence weights so as to center on the heavyweight entities. Finally, the visualization experiments are carried out on the Epinions data set and the performance of the proposed algorithm is compared with the classical force-directed layout algorithm. The experimental results show that it can reveal the nature of communities better.

关键词： Trust network force-directed algorithms layout techniques trust distance Nonprofit Organizations trust Trust Visualization placement algorithm

来源：评论

学校读者我要写书评

暂无评论

One-dimensional layout optimization, with applications to graph drawing by axis separation

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2005年第2期32卷 115-138页

作者： Koren, Y Harel, D AT&T Labs Res Florham Pk NJ USA Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel

In this paper we discuss a useful family of graph drawing algorithms, characterized by their ability to draw graphs in one dimension. We define the special requirements from such algorithms and show how several graph drawing techniques can be extended to handle this task. In particular, we suggest a novel optimization algorithm that facilitates using the Kamada and Kawai model [Inform. Process. Lett. 31 (1989) 7-15] for producing one-dimensional layouts. The most important application of the algorithms seems to be in achieving graph drawing by axis separation, where each axis of the drawing addresses different aspects of aesthetics. (c) 2005 Elsevier B.V. All rights reserved.

关键词： graph drawing force-directed algorithms stress energy multidimensional scaling principal component analysis eigenprojection digraph drawing Newton-Raphson method

来源：评论

学校读者我要写书评

暂无评论

Non-Euclidean spring embedders

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2005年第6期11卷 757-767页

作者： Kobourov, SG Wampler, K Univ Arizona Dept Comp Sci Tucson AZ 85721 USA Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA

We present a conceptually simple approach to generalizing force-directed methods for graph layout from Euclidean geometry to Riemannian geometries. Unlike previous work on non-Euclidean force-directed methods, ours is not limited to special classes of graphs, but can be applied to arbitrary graphs. The method relies on extending the Euclidean notions of distance, angle, and force-interactions to smooth non-Euclidean geometries via projections to and from appropriately chosen tangent spaces. In particular, we formally describe the calculations needed to extend such algorithms to hyperbolic and spherical geometries. We also study the theoretical and practical considerations that arise when working with non-Euclidean geometries.

关键词： force-directed algorithms spring embedders non-Euclidean geometry hyperbolic space spherical space graph drawing information visualization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：