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

A fast successive over-relaxation algorithm for force-directed network graph drawing

Science China(Information Sciences) 2012年第3期55卷 677-688页

作者： WANG YongXian & WANG ZhengHua National Key Laboratory for Parallel and Distributed Processing, National University of Defense Technology, Changsha 410073, China 1. National Key Laboratory for Parallel and Distributed Processing National University of Defense Technology Changsha 410073 China

force-directed approach is one of the most widely used methods in graph drawing research. There are two main problems with the traditional force-directed algorithms. First, there is no mature theory to ensure the convergence of iteration sequence used in the algorithm and further, it is hard to estimate the rate of convergence even if the convergence is satisfied. Second, the running time cost is increased intolerablely in drawing largescale graphs, and therefore the advantages of the force-directed approach are limited in practice. This paper is focused on these problems and presents a sufficient condition for ensuring the convergence of iterations. We then develop a practical heuristic algorithm for speeding up the iteration in force-directed approach using a successive over-relaxation (SOR) strategy. The results of computational tests on the several benchmark graph datasets used widely in graph drawing research show that our algorithm can dramatically improve the performance of force-directed approach by decreasing both the number of iterations and running time, and is 1.5 times faster than the latter on average.

关键词： graph drawing graph layout successive over-relaxation force-directed algorithm

来源：评论

学校读者我要写书评

暂无评论

Clustering-based force-directed algorithms for 3D graph visualization

引用

JOURNAL OF SUPERCOMPUTING 2020年第12期76卷 9654-9715页

作者： Lu, Jiawei Si, Yain-Whar Univ Macau Dept Comp & Informat Sci Ave Univ Taipa Macau Peoples R China

force-directed algorithm is one of the most commonly used methods for visualization of 2D graphs. These algorithms can be applied to a plethora of applications such as data visualization, social network analysis, crypto-currency transactions, and wireless sensor networks. Due to their effectiveness in visualization of topological data, various force-directed algorithms for 2D graphs were proposed in recent years. Although force-directed algorithms for 2D graphs were extensively investigated in research community, the algorithms for 3D graph visualization were rarely reported in the literature. In this paper, we propose four novel clustering-based force-directed (CFD) algorithms for visualization of 3D graphs. By using clustering algorithms, we divide a large graph into many smaller graphs so that they can be effectively processed by force-directed algorithms. In addition, weights are also introduced to further enhance the calculation for clusters. The proposed CFD algorithms are tested on 3 datasets with varying numbers of nodes. The experimental results show that proposed algorithms can significantly reduce edge crossings in visualization of large 3D graphs. The results also reveal that CFD algorithms can also reduce Kamada and Kawai energy and standardized variance of edge lengths in 3D graph visualization.

关键词： 3D graphs Visualization Clustering algorithm force-directed algorithm

来源：评论

学校读者我要写书评

暂无评论

General thermal force model with experimental studies

引用

IEEE TRANSACTIONS ON COMPONENTS AND PACKAGING TECHNOLOGIES 2006年第1期29卷 20-29页

作者： Lee, J So Taiwan Univ Technol Dept Elect Engn Tainan 701 Taiwan

Thermal force has proven to be a useful concept for managing the package-level thermal placement problem. However, the previous thermal force model is based on insulated edge boundary condition;thus it is only suitable to face-cooled packages. A general thermal force model is proposed to extend the applicability of the thermal force to cover general cooling conditions by introducing the concept of the heat transparency of a boundary tau. By managing tau, the present method generates a series of thermal-force-equilibrium placements fitting to situations from face-cooled to edge-cooled packages. Experimental results indicate that for generating the reliability-best placements, the best tau's are in the range 0 <= tau <= 0.05 for face-cooled packages and in the range 0.1 <= 7 <= 0.25 for the volumetric-cooled packages. For edge-cooled packages, the best tau's are the largest values of tau that can achieve convergent thermal-force-equilibrium placements.

关键词： force-directed algorithm reliability thermal force thermal placement

来源：评论

学校读者我要写书评

暂无评论

Graph Drawing by force-directed Method in Mirror Frames

Graph Drawing by Force-Directed Method in Mirror Frames

引用

2nd International Workshop on Database Technology and Applications (DBTA)

作者： Lee, Jing Pei, Ching-Hsing So Taiwan Univ Dept Elect Engn Yun Kang City Tainan Taiwan

ISBN: (纸本)9781424469772

The most widely used algorithms for graph drawing are force-directed algorithms. We should modify a hybrid force model that is coupling a traditional spring force model and a novel repulsive force model will be proposed to solve the graph drawing problems in 2-D space. Especially, regular triangle drawing frame can be applied to binary tree drawing problems that on an important contribution to computer science. And apply circle drawing frame to normal graph drawing problems, we get satisfactory and aesthetic criteria graphics

关键词： graph drawing force-directed algorithm repulsive force model hybrid force model frame

来源：评论

学校读者我要写书评

暂无评论

Fast layout computation of clustered networks: algorithmic advances and experimental analysis

引用

INFORMATION SCIENCES 2014年 260卷 185-199页

作者： Didimo, Walter Montecchiani, Fabrizio Univ Perugia Dipartimento Ingn Elettron & Informaz I-06100 Perugia Italy

The visual analysis of large and complex relational data sets is a growing need in many application domains, such as social sciences, biology, computer networks, and software engineering. In this respect, the capability of quickly computing two-dimensional layouts of hierarchically clustered networks plays an important role and should be a major requirement of many graph visualization systems. We present algorithmic and experimental advances on the subject, namely: (i) we propose a new drawing algorithm that combines space-filling and fast force-directed methods;it runs in O(n log n + m) time, where n and m are the number of vertices and edges of the network, respectively. This running time does not depend on the number of clusters, thus the algorithm guarantees good time performance independently of the structure of the cluster hierarchy. As a further advantage, the algorithm can be easily parallelized. (ii) We discuss the results of an experimental analysis aimed at understanding which clustering algorithms can be used in combination with our visualization technique to generate better quality drawings for small-world and scale-free networks of medium and large size. As far as we know, no previous similar experiments have been done to this aim. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Graph drawing Network visualization Hierarchical clustering Multi-scale algorithm force-directed algorithm Treemap algorithm

来源：评论

学校读者我要写书评

暂无评论

Reliability and wireability optimizations for chip placement on multichip modules

引用

IEEE TRANSACTIONS ON ELECTRONICS PACKAGING MANUFACTURING 2005年第2期28卷 133-141页

作者： Lee, J So Taiwan Univ Technol Dept Elect Engn Tainan 710 Taiwan

The chip placement problem of multichip module (MCM) designs is to map the chips properly to the chip sites on the MCM substrate. Chip placement affects not only the thermal characteristics of an MCM but also routing efficiency, which translates directly into manufacturability, performance, and cost. This paper presents a solution methodology for the optimal placement problem considering both thermal and routing design objectives simultaneously. The coupling is achieved through use of a hybrid-force model that is a combination of the traditional interconnection-force model and a novel thermal-force model. The placement procedure can be used as a design tool to place chips and then determine the tradeoffs which can be made in placing for reliability and wireability. Experiments on five examples including three benchmarks show that the present algorithm yields very high-quality results.

关键词： force-directed algorithm multichip module (MCM) placement thermal force

来源：评论

学校读者我要写书评

暂无评论

An image classification approach for hole detection in wireless sensor networks

引用

JOURNAL OF SUPERCOMPUTING 2022年第6期78卷 8774-8809页

作者： Cheong, Se-Hang Ng, Kim-Hou Si, Yain-Whar Univ Macau Fac Sci & Technol Macau Peoples R China

Hole detection is a crucial task for monitoring the status of wireless sensor networks (WSN) which often consist of low-capability sensors. Holes can form in WSNs due to the problems during placement of the sensors or power/hardware failure. In these situations, sensing or transmitting data could be affected and can interrupt the normal operation of the WSNs. It may also decrease the lifetime of the network and sensing coverage of the sensors. The problem of hole detection is especially challenging in WSNs since the exact location of the sensors is often unknown. In this paper, we propose a novel hole detection approach called FD-CNN which is based on force-directed (FD) algorithm and Convolutional Neural Network (CNN). In contrast to existing approaches, FD-CNN is a centralized approach and is able to detect holes from WSNs without relying on the information related to the location of the sensors. The proposed approach also alleviates the problem of high computational complexity in distributed approaches. The proposed approach accepts the network topology of a WSN as an input and generates the identity of the nodes surrounding each detected hole in the network as the final output. In the proposed approach, an FD algorithm is used to generate the layout of the wireless sensor networks followed by the identification of the holes in the layouts using a trained CNN model. In order to prepare labeled datasets for training the CNN model, an unsupervised pre-processing method is also proposed in this paper. After the holes are detected by the CNN model, two algorithms are proposed to identify the regions of the holes and corresponding nodes surrounding the regions. Extensive experiments are conducted to evaluate the proposed approach based on different datasets. Experimental results show that FD-CNN can achieve 80% sensitivity and 93% specificity in less than 2 minutes.

关键词： Wireless sensor networks Hole detection force-directed algorithm Convolutional neural network

来源：评论

学校读者我要写书评

暂无评论

Self-organizing maps for drawing large graphs

引用

INFORMATION PROCESSING LETTERS 1998年第4期67卷 177-184页

作者： Bonabeau, E Henaux, F Santa Fe Inst Santa Fe NM 87501 USA ATR Adapt Commun Res Kyoto 61902 Japan Ecole Natl Super Telecommun F-75634 Paris France

Self-organizing maps (SOM) are unsupervised, competitive neural networks used to project high-dimensional data onto a low-dimensional space. In this article we show how SOM can be used to draw graphs in the plane. The SOM-based approach to graph drawing, which belongs to the general class of force-directed algorithms, allows the drawing of arbitrary weighted graphs. It is particularly efficient to draw large graphs and can be used as a preprocessing step before application of a more sophisticated method. (C) 1998 Published by Elsevier Science B.V. All rights reserved.

关键词： neural networks self-organizing maps graph drawing force-directed algorithm algorithms

来源：评论

学校读者我要写书评

暂无评论

CWBound: boundary node detection algorithm for complex non-convex mobile ad hoc networks

引用

JOURNAL OF SUPERCOMPUTING 2018年第10期74卷 5558-5577页

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

Efficient message forwarding in mobile ad hoc network in disaster scenarios is challenging because location information on the boundary and interior nodes is often unavailable. Information related to boundary nodes can be used to design efficient routing protocols as well as to prolong the battery power of devices along the boundary of an ad hoc network. In this article, we developed an algorithm, CWBound, which discovers boundary nodes in a complex non-convex mobile ad hoc (CNCAH) networks. Experiments show that the CWBound algorithm is at least three times faster than other state-of-the-art algorithms, and up to 400 times faster than classical force-directed algorithms. The experiments also confirmed that the CWBound algorithm achieved the highest accuracy (above 97% for 3 out of the 4 types of CNCAH networks) and sensitivity (90%) among the algorithms evaluated.

关键词： Mobile ad hoc network force-directed algorithm Boundary node detection Complex non-convex ad hoc network

来源：评论

学校读者我要写书评

暂无评论

Planning-oriented optimization strategy for visualizing power distribution networks:from global to local

引用

International Journal of Digital Earth 2021年第12期14卷 1775-1797页

作者： Rui Li Bingzhen Chen Guangsheng Dong Huayi Wu State Key Laboratory of Information Engineering in Surveying Mapping and Remote SensingWuhan UniversityWuhanHubeiPeople’s Republic of China

The spatial distribution of power facilities is uneven,thereby making the topology of geographical wiring diagrams(GWDs)based on the actual coordinates unclear.A single-line diagram has the advantage of a clear topology but it lacks spatial locations.A GWD has the advantage of accurate spatial locations but it lacks a clear *** distribution networks for planning requires both *** proposed a new planning-oriented method for optimizing the visualization of distribution *** the global perspective,we proposed an improved force-directed(FD)algorithm by introducing a space restriction strategy and node–edge repulsion strategy to promote the expansion of the distance between distribution facilities within a limited *** then constructed the constrained Delaunay triangulation to identify the compact districts(CDs)and used a genetic algorithm to optimize the parameters for the improved FD algorithm.A novel visualization evaluation indicator was also proposed for quantitatively assessing the *** a local perspective,the fisheye algorithm was used to optimize the CDs to further improve the visualization of the distribution *** verified the proposed methods with real-world *** used limited spatial displacement in exchange for maximum topology clarity to balance the accurate spatial location and topology clarity.

关键词： Visualization optimization geographical wiring diagrams force-directed algorithm fisheye algorithm genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：