Embedding graphs under centrality constraints
2013-05
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Embedding graphs under centrality constraints
Authors
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
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.