school

UM E-Theses Collection (澳門大學電子學位論文庫)

check Full Text
Title

Force-directed algorithms for graph visualization

English Abstract

Force-directed algorithms have been developed over the last 50 years and used in many application fields, including information visualization, biological network visualization, sensor networks, routing algorithms, scheduling, graph drawing, etc. Each of these applications relates to information visualization broadly. Information visualization allows users to make better sense of network relationships than by simply looking at data in tabular form. However, unsupervised visualization cannot meet these objectives. How network topologies are drawn can significantly affect how viewers understand the network. The layout and position-assignment of visualized network nodes influence how a user perceives network relationships. The first part of the thesis aims to provide a comprehensive summary of the merits and deficiencies of force-directed algorithms and visualization applications. We discussed the influences caused by the layout and position-assignment of visualized network nodes on how a user perceives the relationships in the network. We also evaluated the quality of snapshots generated from force-directed algorithms in terms of the number of edge crossing and the standard deviations of edge length in order to review and analyze the performance of available force-directed algorithms for graph visualization. The use of wireless sensor network in disaster scenarios has been extensively studied in recent years. By locating boundary nodes, we can design energy-efficient messaging schedules in which interior nodes can be turned off occasionally to increase the throughput. The boundary nodes of a mobile ad hoc network are the outer nodes of a graph. Therefore, the boundary detection problem of a mobile ad hoc network can be reformulated as a problem of visualizing the topology of the respective graph. CWBound algorithm is proposed for the boundary node detection in complex nonconvex mobile ad hoc (CNCAH) networks. The CWBound algorithm was evaluated against the KK, DH, FR, FRR, FA2 and KK-MS-DS algorithms. Our experimental results show that the CWBound algorithm achieved the highest sensitivity of these algorithms in all benchmark CNCAH networks. The CWBound algorithm also required significantly shorter processing times. The CWBound algorithm is 3 to 5 times faster than the KK-MS-DS algorithm, and 60 to 400 times faster than the original KK algorithm in achieving 90% sensitivity in the four type of CNCAH networks we evaluated.

Issue date

2021.

Author

Cheong, Se Hang

Faculty

Faculty of Science and Technology

Department

Department of Computer and Information Science

Degree

Ph.D.

Subject

Computer science

Computer graphics

Information visualization

Supervisor

Si, Yain Whar

Files In This Item

Full-text (Intranet only)

Location
1/F Zone C
Library URL
991010082327306306