Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Thesis_Sungmin_ohiolink.pdf (21.17 MB)

ETD Abstract Container

Abstract Header

Community Detection in Directed Networks and its Application to Analysis of Social Networks

Kim, Sungmin
http://rave.ohiolink.edu/etdc/view?acc_num=osu1397571499

Abstract Details

2014, Doctor of Philosophy, Ohio State University, Statistics.
Community detection has been one of the central problems in network studies. Detecting communities in a directed network is particularly challenging due to the directionality in its links. In this thesis, we show that incorporating the direction of links reveals new perspectives on communities regarding to two different roles, source and terminal, that a node may play in a community. A novel concept of a community in a directed network, called directional community, is proposed, and its relation to a connectivity in directed networks and a quality measure of a community are investigated. Intriguingly, directional communities appear to be closely related to a unique spectral property of the graph Laplacian matrix and we exploit this connection using regularized SVD methods. We propose harvesting algorithms, coupled with the regularized SVDs, that are linearly scalable for efficient identification of directional communities in a massive directed network. In addition, we construct another class of algorithms that exploits the connectivity in directed networks and makes use of existing community detection algorithms intended for undirected networks. The proposed algorithms show remarkable performance and scalability on simulated benchmark networks and successfully recover communities in real network applications with more than millions of nodes. The actual running time of the algorithms for a network with a million links is less than an hour. The algorithms are applied to the task of analyzing community structures in massive social networks, which is of particular interest since a community in a social network reflects a group of users that demonstrates dense interactions within the group. Our proposed algorithms address two challenges in community detection in a large social network, 1) how to incorporate the directions of interactions, 2) how to search for communities in networks of millions of users. As an effort to obtain a social network with intrinsic community structures, the social interactions of sports fans, particularly of NCAA college football teams, are collected from a popular social media service, Twitter. The obtained social interaction network is a large directed network, which has about a half-million nodes and links. Proposed algorithms successfully identified the communities of the fans of each football team. In comparison to the existing community detection algorithms, our proposed methods successfully distinguish the two different roles of fans, celebrity types and supporters types.
Tao Shi, Dr. (Advisor)
Yoonkyong Lee, Dr. (Committee Member)
Vince Vu, Dr. (Committee Member)
157 p.
Statistics
Community extraction, Graph Laplacian, Regularized SVD, Scalable algorithm, Social networks

Recommended Citations

Citations

  • Kim, S. (2014). Community Detection in Directed Networks and its Application to Analysis of Social Networks [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1397571499

    APA Style (7th edition)

  • Kim, Sungmin. Community Detection in Directed Networks and its Application to Analysis of Social Networks. 2014. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1397571499.

    MLA Style (8th edition)

  • Kim, Sungmin. "Community Detection in Directed Networks and its Application to Analysis of Social Networks." Doctoral dissertation, Ohio State University, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=osu1397571499

    Chicago Manual of Style (17th edition)

osu1397571499
359
© 2014, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.