On Structural Analysis of Large Networks

Containing much valuable information, networks such as the World Wide Web, social networks and metabolic networks draw increasingly attention in scientific communities. Network clustering (or graph partitioning) is the discovery of underlying clusters of related vertices in networks. But beyond organizing vertices into clusters of peers is the question of what role each vertex play in the network. This paper presents some new ways of uncovering underlying structures, including the roles that vertices play in the network. Identifying vertex roles is useful for applications such as viral marketing and epidemiology. For example, hubs are responsible for spreading ideas or disease. We applied our algorithm to analyze some real networks. The results demonstrate a superior performance over other methods such as modularity-based algorithms.