File(s) under permanent embargo
Keyword-based correlated network computation over large social media
conference contribution
posted on 2014-01-01, 00:00 authored by Jianxin LiJianxin Li, Chengfei Liu, Md Saiful IslamRecent years have witnessed an unprecedented proliferation of social media, e.g., millions of blog posts, micro-blog posts, and social networks on the Internet. This kind of social media data can be modeled in a large graph where nodes represent the entities and edges represent relationships between entities of the social media. Discovering keyword-based correlated networks of these large graphs is an important primitive in data analysis, from which users can pay more attention about their concerned information in the large graph. In this paper, we propose and define the problem of keyword-based correlated network computation over a massive graph. To do this, we first present a novel tree data structure that only maintains the shortest path of any two graph nodes, by which the massive graph can be equivalently transformed into a tree data structure for addressing our proposed problem. After that, we design efficient algorithms to build the transformed tree data structure from a graph offline and compute the γ-bounded keyword matched subgraphs based on the pre-built tree data structure on the fly. To further improve the efficiency, we propose weighted shingle-based approximation approaches to measure the correlation among a large number of γ-bounded keyword matched subgraphs. At last, we develop a merge-sort based approach to efficiently generate the correlated networks. Our extensive experiments demonstrate the efficiency of our algorithms on reducing time and space cost. The experimental results also justify the effectiveness of our method in discovering correlated networks from three real datasets.
History
Event
IEEE Computer Society. Conference (30th : 2014 : Chicago, Ill.)Series
IEEE Computer Society ConferencePagination
268 - 279Publisher
Institute of Electrical and Electronics EngineersLocation
Chicago, Ill.Place of publication
Piscataway, N.J.Publisher DOI
Start date
2014-03-31End date
2014-04-04ISBN-13
978-1-4799-2555-1Language
engPublication classification
E1.1 Full written paper - refereedCopyright notice
2014, IEEEEditor/Contributor(s)
[Unknown]Title of proceedings
ICDE 2014 : Proceedings of the 2014 IEEE 30th International Conference on Data EngineeringUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC