Loading...
Please wait, while we are loading the content...
Similar Documents
Graph pattern matching on social network analysis
| Content Provider | Semantic Scholar |
|---|---|
| Author | Wang, Xin |
| Copyright Year | 2013 |
| Abstract | Graph pattern matching is fundamental to social network ana lysis. Its effectiveness for identifying social communities and social positions, m aking recommendations and so on has been repeatedly demonstrated. However, the social network analysis raises new challenges to graph pattern matching. As real-life soci al graphs are typically large, it is often prohibitively expensive to conduct graph pattern matching over such large graphs,e.g., NP-complete for subgraph isomorphism, cubic time for bounded simulation, and quadratic time for simulation. These hinde r th applicability of graph pattern matching on social network analysis. In response to these challenges, the thesis presents a series of effective techniques for querying larg e, dynamic, and distributively stored social networks. First of all, we propose a notion of query preserving graph compression , to compress large social graphs relative to a class Q of queries. We then develop both batch and incremental compression strategies for two commonly us ed pattern queries. Via both theoretical analysis and experimental studies, we sho w t at (1) using compressed graphsGr benefits graph pattern matching dramatically; and (2) the co mputation ofGr as well as its maintenance can be processed efficiently. Secondly, we investigate the distributed graph pattern mat ching problem, and explore parallel computation for graph pattern matching. We s how that our techniques possess following performance guarantees: (1) each site is visitedonly once; (2) the total network traffic isindependent of the size ofG; and (3) the response time is decided by the size of largest fragment of G rather thanthe size of entireG. Furthermore, we show how these distributed algorithms can be implemented in the MapReduce framework. Thirdly, we study the problem of answering graph pattern mat ching using views since view based techniques have proven an effective techni que for speeding up query evaluation. We propose a notion of pattern containmento characterise graph pattern matching using views, and introduce efficient algorith ms to answer graph pattern matching using views. Moreover, we identify three problems related to graph pattern containment, and provide efficient algorithms for containm e t checking (approximation when the problem is intractable). Fourthly, we revise graph pattern matching by supporting a d esignated output node, which we treat as “query focus”. We then introduce algorithm s for computing the topk relevant matches w.r.t. the output node for both acyclic and cyclic pattern graphs, r espectively, withearly termination property . Furthermore, we investigate the diversified |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.era.lib.ed.ac.uk/bitstream/handle/1842/8277/Wang2013.pdf?isAllowed=y&sequence=2 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
