Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for +publisher:"University of Texas – Austin" +contributor:("Gleich, David F"). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


University of Texas – Austin

1. Whang, Joyce Jiyoung. Overlapping community detection in massive social networks.

Degree: Computer Sciences, 2015, University of Texas – Austin

Massive social networks have become increasingly popular in recent years. Community detection is one of the most important techniques for the analysis of such complex networks. A community is a set of cohesive vertices that has more connections inside the set than outside. In many social and information networks, these communities naturally overlap. For instance, in a social network, each vertex in a graph corresponds to an individual who usually participates in multiple communities. In this thesis, we propose scalable overlapping community detection algorithms that effectively identify high quality overlapping communities in various real-world networks. We first develop an efficient overlapping community detection algorithm using a seed set expansion approach. The key idea of this algorithm is to find good seeds and then greedily expand these seeds using a personalized PageRank clustering scheme. Experimental results show that our algorithm significantly outperforms other state-of-the-art overlapping community detection methods in terms of run time, cohesiveness of communities, and ground-truth accuracy. To develop more principled methods, we formulate the overlapping community detection problem as a non-exhaustive, overlapping graph clustering problem where clusters are allowed to overlap with each other, and some nodes are allowed to be outside of any cluster. To tackle this non-exhaustive, overlapping clustering problem, we propose a simple and intuitive objective function that captures the issues of overlap and non-exhaustiveness in a unified manner. To optimize the objective, we develop not only fast iterative algorithms but also more sophisticated algorithms using a low-rank semidefinite programming technique. Our experimental results show that the new objective and the algorithms are effective in finding ground-truth clusterings that have varied overlap and non-exhaustiveness. We extend our non-exhaustive, overlapping clustering techniques to co-clustering where the goal is to simultaneously identify a clustering of the rows as well as the columns of a data matrix. As an example application, consider recommender systems where users have ratings on items. This can be represented by a bipartite graph where users and items are denoted by two different types of nodes, and the ratings are denoted by weighted edges between the users and the items. In this case, co-clustering would be a simultaneous clustering of users and items. We propose a new co-clustering objective function and an efficient co-clustering algorithm that is able to identify overlapping clusters as well as outliers on both types of the nodes in the bipartite graph. We show that our co-clustering algorithm is able to effectively capture the underlying co-clustering structure of the data, which results in boosting the performance of a standard one-dimensional clustering. Finally, we study the design of parallel data-driven algorithms, which enables us to further increase the scalability of our overlapping community detection algorithms. Using… Advisors/Committee Members: Dhillon, Inderjit S. (advisor), Grauman, Kristen (committee member), Mooney, Raymond J (committee member), Pingali, Keshav (committee member), Gleich, David F (committee member).

Subjects/Keywords: Community detection; Clustering; Social networks; Overlapping communities; Overlapping clusters; Non-exhaustive clustering; Seed expansion; K-means; Semidefinite programming; Co-clustering; PageRank; Data-driven algorithm; Scalable computing

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Whang, J. J. (2015). Overlapping community detection in massive social networks. (Thesis). University of Texas – Austin. Retrieved from http://hdl.handle.net/2152/33272

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Whang, Joyce Jiyoung. “Overlapping community detection in massive social networks.” 2015. Thesis, University of Texas – Austin. Accessed June 15, 2019. http://hdl.handle.net/2152/33272.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Whang, Joyce Jiyoung. “Overlapping community detection in massive social networks.” 2015. Web. 15 Jun 2019.

Vancouver:

Whang JJ. Overlapping community detection in massive social networks. [Internet] [Thesis]. University of Texas – Austin; 2015. [cited 2019 Jun 15]. Available from: http://hdl.handle.net/2152/33272.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Whang JJ. Overlapping community detection in massive social networks. [Thesis]. University of Texas – Austin; 2015. Available from: http://hdl.handle.net/2152/33272

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.