Edge partitioning and finding community structure using spectral decomposition.

摘要

Many systems take the form of networks, sets of nodes or vertices joined together in pairs by links or edges. These network structure can be found in diverse fields as engineering, social, economic, and biological systems. Due to the omnipresence of networks, many efforts have been made to uncover the organizing principles that govern the formation and the evolution of various complex networks. One of the important properties of the networks is that of community structure---nodes are often found to cluster into tightly-knit groups with a high density of within-group edges and lower density of between-group edges. This community structure of the networks performs an important role in the study of networks. We proposed a new method for detecting such community, using the spectral decomposition, and it overcomes shortcomings of the conventional spectral partitioning approaches such as min-cut, and max-cut. We show this method can be a powerful approach for finding the community structure in the networks. We apply this method to the computer generated networks and real-world networks and show the advantages of the proposed method. We analyze personal emails in the form of network data and proposed a new approach for classifying spam and non-spam emails based on graph theoretic approaches. The proposed algorithm can distinguish between unsolicited commercial emails, so called spam and non-spam emails using only the information in the email headers. We exploit the properties of social networks and spectral decomposition to implement our algorithm. In this study, we mainly used the community structure in social network to classify non-spam and proposed a new method for edge partition of networks. We tested our method on a users's mail box, and it classified 41% of all emails as spam or non-spam emails, with no error. And these results are obtained with only few subnetworks resulted from the proposed decomposition method. It requires no supervised training and solely based on the properties of networks, not on the contents of emails.