| Social networks are ubiquitous. They can be extracted from our purchase history at on-line retailers, our cellphone bills, and even our health records. Mining techniques that can accurately and efficiently identify interesting patterns in these networks are sought after by researchers from a variety of fields. The patterns they seek often take the shape of communities, which are tightly-knit groups of nodes that are more strongly related within the group than outside of the group.;This thesis proposes a series of algorithms that both accurately identify and evaluate communities in social networks. In particular we show that relative validity criteria from the field of database clustering do not serve as adequate substitutes in lieu of a ground truth. Furthermore we propose a novel community mining algorithm that considers the number of internal and external triads within each community. Finally, we present two visualization algorithms that visually expose previously difficult to obtain information regarding the structure and relationships of communities. We conclude this thesis with a brief summary of some open problems in the area of community mining and visualization. |
