图 书 馆
在大归因图快速尽力而为模式匹配Fast Best-Effort Pattern Matching in Large Attributed Graphs |
|
| 课程网址: | http://videolectures.net/kdd07_tong_fbep/ |
| 主讲教师: | Hanghang Tong |
| 开课单位: | 亚利桑那州立大学 |
| 开课时间: | 2007-08-14 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We focus on large graphs where nodes have attributes, such as a social network where the nodes are labelled with each person’s job title. In such a setting, we want to find subgraphs that match a user query pattern. For example, a ‘star’ query would be, “find a CEO who has strong interactions with a Manager, a Lawyer, and an Accountant, or another structure as close to that as possible”. Similarly, a ‘loop’ query could help spot a money laundering ring. Traditional SQL-based methods, as well as more recent graph indexing methods, will return no answer when an exact match does not exist. Our method can find exact-, as well as near-matches, and it will present them to the user in our proposed ‘goodness’ order. For example, our method tolerates indirect paths between, say, the ‘CEO’ and the ‘Accountant’ of the above sample query, when direct paths do not exist. Its second feature is scalability. In general, if the query has nq nodes and the data graph has n nodes, the problem needs polynomial time complexity O(nnq ), which is prohibitive. Our G-Ray (“Graph X-Ray”) method finds high-quality subgraphs in time linear on the size of the data graph. Experimental results on the DLBP author-publication graph (with 356K nodes and 1.9M edges) illustrate both the effectiveness and scalability of our approach. The results agree with our intuition, and the speed is excellent. It takes 4 seconds on average for a 4- node query on the DBLP graph. |
| 关 键 词: | 计算机科学; 机器学习; 模式识别 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-06-24：yumf |
| 阅读次数: | 48 |