| |
|
|
|
| |
|
|
|
|
|
|
|
|
| |
Traditional methods for network analysis leverage properties of random walks to identify central nodes or to partition the network into communities of tightly knit nodes. Take for example spectral analysis, a long-studied area of graph theory with many applications in image segmentation, data mining, and community detection in social and biological networks.
Spectral graph partitioning relates the eigenvalue spectrum of the graph Laplacian, an operator that is closely associated with random walks of graphs, to topological properties of the graph, such as minimum conductance cut. While computing conductance can be computationally expensive, relationships between random walk-based centrality and conductance form the basis for efficient local graph partitioning algorithms.
|
|
| |
|
|
|
| |
Besides random walks, many other types of dynamic processes exist, such as epidemic diffusion, motivating new spectral methods. We will develop a generalized framework for describing dynamic processes on networks. This framework represents a dynamic process as an operator with its own eigenspectrum and relates its properties to network structure, allowing for generalizations of relationships between algebraic and topological properties of graphs. This has a number of important applications, including new methods for spectral graph partitioning, and fast local partitioning with provable bounds.
|
|
| |
|
|
|
| |
|
|
| |
|
|
|
|
|
|
| |
|
|
|
| |
|
| |
|
|
|
| |
Click here for updated list of project-related publications. |
|
| |
|
|
|
|
|
|
| |
|
|
|
| |
|
| |
|
|
|
| |
Kristina Lerman, PI (USC)
Laura M. Smith, Post-doctoral Research Associate (USC)
|
|
| |
|
|
|
| |
This research is sponsored by the National Science Foundation (award numbers CIF-1217605 and 0915678). |
|
| |
|
|
|
