Knowledge Graph Enhanced Community Detection and Characterization

TitleKnowledge Graph Enhanced Community Detection and Characterization
Publication TypeConference Paper
Year of Publication2019
AuthorsShreyansh Bhatt, Swati Padhee, Amit Sheth, Keke Chen, Valerie Shalin, Derek Doran, Brandon Minnery
Conference NameTwelfth ACM International Conference on Web Search and Data Mining
Pagination51-59
Date Published02/2019
PublisherACM
Conference LocationMelbourne, Australia
Keywordscommunity detection, knowledge graph, social media analysis
Abstract

Recent studies show that by combining network topology and node attributes, we can better understand community structures in complex networks. However, existing algorithms do not explore “contextually” similar node attribute values, and therefore may miss communities defined with abstract concepts. We propose a community detection and characterization algorithm that incorporates the contextual information of node attributes described by multiple domain specific hierarchical concept graphs. The core problem is to find the context that can best summarize the nodes in communities, while also discovering communities aligned with the context summarizing communities. We formulate the two inter-twined problems, optimal community-context computation, and community discovery, with a coordinate-ascent based algorithm that iteratively updates the nodes’ community label assignment with a community-context and computes the best context summarizing nodes of each community. Our unique contributions include(1) a composite metric on Informativeness and Purity criteria in searching for the best context summarizing nodes of a community;(2) a node similarity measure that incorporates the context-level similarity on multiple node attributes; and (3) an integrated algorithm that drives community structure discovery by appropriately weighing edges. Experimental results on public datasets show nearly 20percent improvement on F-measure and Jaccard for discovering underlying community structure over the current state-of-the-art of community detection methods. Community structure characterization was also accurate to !nd appropriate community types for four datasets. Moreover, our algorithm yields insightful community structures that explain the contextual relationships among communities, which helps us better understand two real-world applications of social networks.

Full Text

Citation:
Shreyansh Bhatt, Swati Padhee, Amit Sheth, Keke Chen, Valerie Shalin, Derek Doran, and Brandon Minnery. "Knowledge Graph Enhanced Community Detection and Characterization." In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 51-59. ACM, 2019.

Projects: 
Harassment
Related Files: