Community Mining: from Discovery to Evaluation and Visualization

• Author / Creator

  Fagnan, Justin J

• 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 tech-
  niques that can accurately and efficiently identify interesting patterns in these net-
  works 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 valid-
  ity 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 al-
  gorithm that considers the number of internal and external triads within each com-
  munity. Finally, we present two visualization algorithms that visually expose pre-
  viously 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.

• Subjects / Keywords

  • Community mining
  • Relative validity criteria
  • Social network analysis
  • Community visualization
  • Local community framework

• Graduation date

  Spring 2012

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R31C9C

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.