Embedding graphs under centrality constraints

Loading...
Thumbnail Image

Persistent link to this item

Statistics
View Statistics

Journal Title

Journal ISSN

Volume Title

Title

Embedding graphs under centrality constraints

Published Date

2013-05

Publisher

Type

Thesis or Dissertation

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.

Description

University of Minnesota M.S. thesis. May 2013. Major: Electrical/Computer Engineering. Advisor: Professor: Georgios B. Giannakis. 1 computer file (PDF); v, 46 pages, appendices A-B.

Related to

Replaces

License

Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Other identifiers

Suggested citation

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

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.