Convex optimization techniques can be applied to many problems. In this exercise we investigated algebraic connectivity of graphs. First, we formulated the problem of finding edge weights that maximize algebraic connectivity as a convex optimization problem. And second, we used a numerical example to calculate and compare the algebraic connectivity of a graph with optimal edge weights versus uniform constant edge weights. We concluded that optimal edge weights lead to better algebraic connectivity, because important edges carry greater weight and therefore, significantly improve the overall graph connectivity. Using this numerical example we demonstrated that greater number of edges does not necessarily lead to greater algebraic connectivity. Instead, optimal edge weights are more important.
ekloberdanz/AlgebraicGraphConnectivity
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
About
Convex Optimization Solution of Maximum Algebraic Connectivity of a Graph. The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue) of a graph G is the second smallest eigenvalue of the Laplacian matrix of G.
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published