Back to search

University of Minnesota

Embedding graphs under centrality constraints

Abstract

dc:description.abstract

Visual rendering of graphs is a key task in the mapping of complex network data. Although most graph drawing algorithms emphasize aesthetic appeal, certain applications such as travel-time maps place more importance on visualization of structural network properties. This thesis advocates two graph embedding approaches with centrality considerations to comply with node hierarchy. The embedding problem is formulated first as one of constrained multi-dimensional scaling (MDS), and it is solved via block coordinate descent iterations with successive approximations and guaranteed convergence to a Karush-Kuhn-Tucker (KKT) point. In addition, a regularization term enforcing graph smoothness is incorporated with the goal of reducing edge crossings. A second approach leverages the locally-linear embedding (LLE) algorithm which assumes that the graph encodes data sampled from a low-dimensional manifold. Closed-form solutions to the resulting centrality-constrained optimization problems are determined yielding meaningful embeddings. Experimental results demonstrate the efficacy of both approaches, especially for visualizing large networks on the order of thousands of nodes.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Baingana, Brian

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Citation
Baingana, Brian. (2013). Embedding graphs under centrality constraints. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/157291.

Chain of custody

source
Harvested from
University of Minnesota
Base URL
conservancy.umn.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Baingana, Brian. Embedding graphs under centrality constraints. 2013. http://purl.umn.edu/157291