國立高雄大學圖資館 |

Language: English

Back

Designing well-connected networks.

Ghosh, Arpita.

Designing well-connected networks.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Designing well-connected networks.
Author:	Ghosh, Arpita.
Description:	142 p.
Notes:	Adviser: Stephen P. Boyd.
Notes:	Source: Dissertation Abstracts International, Volume: 67-05, Section: B, page: 2739.
Contained By:	Dissertation Abstracts International67-05B.
Subject:	Engineering, Electronics and Electrical.
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3219279
ISBN:	9780542706806

Designing well-connected networks.
Ghosh, Arpita.

Designing well-connected networks. - 142 p.

Adviser: Stephen P. Boyd.

Thesis (Ph.D.)--Stanford University, 2006.

This thesis studies several optimization problems related to designing well-connected networks.

ISBN: 9780542706806Subjects--Topical Terms:

226981
Engineering, Electronics and Electrical.

Designing well-connected networks.
LDR:02906nmm _2200277 _450 001 180569
005 20080111103740.5
008 090528s2006 eng d
020 $a 9780542706806
035 $a 00311594
040 $a UMI $c UMI
100 0 $a Ghosh, Arpita. $3 264144
245 1 0 $a Designing well-connected networks.
300 $a 142 p.
500 $a Adviser: Stephen P. Boyd.
500 $a Source: Dissertation Abstracts International, Volume: 67-05, Section: B, page: 2739.
502 $a Thesis (Ph.D.)--Stanford University, 2006.
520 # $a This thesis studies several optimization problems related to designing well-connected networks.
520 # $a We first discuss two optimization problems where the variables are weights, or probabilities, on the edges of the network graph. The first is designing randomized gossip algorithms for fast distributed averaging on an arbitrary network. We show that the averaging time depends on the second largest eigenvalue of the stochastic matrix characterizing the averaging algorithm, and pose the problem of finding the fastest such algorithm as a semidefinite program (SDP). The second problem is to find the reversible random walk with the smallest average commute time on a given graph. Using the relation between effective resistance and commute time, we show that this is a convex optimization problem as well, and can be formulated as an SDP. The convexity of these problems has both theoretical and practical implications: they can be efficiently solved numerically, and we can exploit convexity to derive interesting analytical results for these problems.
520 # $a We next study two problems related to the algebraic connectivity of a graph, which is the second smallest eigenvalue of the graph Laplacian. First we consider the problem of adding edges to an unweighted graph to increase its algebraic connectivity. The problem of choosing the best k edges of a given set of m candidate edges is combinatorial; we describe a heuristic for adding edges based on the Fiedler vector which performs very well, and is easily computed even for very large graphs. Second, we study the problem of computing upper bounds on the algebraic connectivity over a family of graphs. We show that an upper bound can be computed as the solution to a convex optimization problem. By observing that it suffices to optimize over the subset of matrices invariant under the symmetry group of the set of graphs, we can solve the optimization problem analytically for families of graphs with large enough symmetry groups.
590 $a School code: 0212.
650 # 0 $a Engineering, Electronics and Electrical. $3 226981
690 $a 0544
710 0 # $a Stanford University. $3 212607
773 0 # $g 67-05B. $t Dissertation Abstracts International
790 $a 0212
790 1 0 $a Boyd, Stephen P., $e advisor
791 $a Ph.D.
792 $a 2006
856 4 0 $u http://libsw.nuk.edu.tw:81/login?url=http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3219279 $z http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3219279