University of Southern California


ISI Site Signature




Kristina Lerman
 
 
       
  Rethinking Network Structure: The Role of Interactions in the Analysis of Network Structure  
  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, representing a variety of interactions between nodes, exist on networks. Consider, for example, epidemic diffusion, which rather than infecting a single random neighbor of a given node attempts to infect all neighbors. The nodes that are visited most often by a random walk (central nodes) will be different from the nodes that are infected most frequently during an epidemic, as shown in the figure below. We have developed 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.  
     
   
       

       
  Publications  
       
  Click here for updated list of project-related publications.  
       

       
  Project Staff  
       
  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).