检索结果-内蒙古大学图书馆

graph simulation on large scale temporal graphs

GEOINFORMATICA 2020年第1期24卷 199-220页

作者： Ma, Yuliang Yuan, Ye Liu, Meng Wang, Guoren Wang, Yishu Northeastern Univ Shenyang Liaoning Peoples R China Beijing Inst Technol Beijing Peoples R China

graph simulation is one of the most important queries in graph pattern matching, and it is being increasingly used in various applications, e.g., protein interaction networks, software plagiarism detection. Most previous studies mainly focused on the simulation problem on static graphs, which neglected the temporal factors in daily life. In this paper, we investigate a novel problem, namely, temporal bounded simulation on temporal graphs. Specifically, given a pattern query Q with bound constraint and a temporal graph G, we aim to find out the matches Q(G) of Q on G, such that Q(G) satisfies temporal reachability and bound constraint of Q. To tackle this problem efficiently, we propose a simulation matching framework, which consists of three phases, namely pattern segmentation, temporal bounded simulation of pattern segments, and result integration. We first divide the Q into simple small subgraphs (segments). We construct a temporal reachable tree of G. Based on the tree, we propose a basic matching algorithm for the pattern segments. Furthermore, we propose two optimization algorithms by leveraging multi-layer partition strategy to accelerate query processing. After that, we integrate the simulation results obtained from the pattern segments according to the constraints of temporal reachability and the bound of query pattern. Finally, we use real temporal and synthetic datasets to empirically verify the efficiency and effectiveness of our solutions for temporal bounded simulation matching.

关键词： graph simulation Pattern match Temporal graph

来源：评论

学校读者我要写书评

暂无评论

Diversified top-k search with relaxed graph simulation

引用

SOCIAL NETWORK ANALYSIS AND MINING 2019年第1期9卷 1-15页

作者： Habi, Abdelmalek Effantin, Brice Kheddouci, Hamamache Univ Lyon 1 Univ Lyon CNRS UMR 5205LIRIS F-69622 Lyon France

graph pattern matching has been widely used in a broad spectrum of real-world applications, and it has been the subject of several investigations, mainly of its importance and use. In this context, different models along with their appropriate algorithms have been proposed. However, in addition to the excessive processing costs, most of the existing models suffer from the failing query problem due to their limitations on finding meaningful matches. Also, in some scenarios, the number of matches may be enormous, making the inspection a daunting task. In this work, we introduce a new model for graph pattern matching, called relaxed graph simulation (RGS), allowing the relaxation of queries to identify more significant matches and to avoid the empty-set answer problem. We then formalize and study the top-k matching problem based on two function classes, relevance and diversity, for ranking the matches with respect to the proposed model. We also formalize and investigate the diversified top-k matching problem, and we propose a diversification function to balance relevance and diversity. Nonetheless, we provide efficient algorithms based on optimization strategies to compute the top-k and the diversified top-k matches according to the RGS model. Our experimental results, on four real datasets, demonstrate both the effectiveness and the efficiency of the proposed approaches.

关键词： graph pattern matching Relaxed graph simulation graph simulation Top-k Diversified top-k Social networks

来源：评论

学校读者我要写书评

暂无评论

Fast top-k search with relaxed graph simulation 10

Fast top-<i>k</i> search with relaxed graph simulation

引用

IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)

作者： Habi, Abdelmalek Effantin, Brice Kheddouci, Hamamache Univ Claude Bernard Lyon 1 Univ Lyon CNRS LIRIS F-69622 Lyon France

ISBN: (纸本)9781538660515

graph pattern matching has been widely used in large spectrum of real applications. In this context, different models along with their appropriate algorithms have been proposed. However, a major drawback on existing models is their limitation to find meaningful matches resulting in a number of failing queries. In this paper we introduce a new model for graph pattern matching allowing the relaxation of queries in order to avoid the empty-answer problem. Then we develop an efficient algorithm based on optimization strategies for computing the top-k matches according to our model. Our experimental evaluation on four real datasets demonstrates both the effectiveness and the efficiency of our approach.

关键词： graph pattern matching relaxed graph simulation graph simulation top-k social networks

来源：评论

学校读者我要写书评

暂无评论

Maximum Entropy Distributions with Applications to graph simulation

引用

OPERATIONS RESEARCH 2023年第5期71卷 1908-1924页

作者： Glasserman, Paul de Larrea, Enrique Lelo Columbia Univ Grad Sch Business New York NY USA Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA

We study the problem of sampling uniformly from discrete or continuous product sets subject to linear constraints. This family of problems includes sampling weighted bipartite, directed, and undirected graphs with given degree sequences. We analyze two candidate distributions for sampling from the target set. The first one maximizes entropy subject to satisfying the constraints in expectation. The second one is the distribution from an exponential family that maximizes the minimum probability over the target set. Our main result gives a condition under which the maximum entropy and the max-min distributions coincide. For the discrete case, we also develop a sequential procedure that updates the maximum entropy distribution after some components have been sampled. This procedure sacrifices the uniformity of the samples in exchange for always sampling a valid point in the target set. To address the loss of uniformity, we use importance sampling weights. The quality of these weights is affected by the order in which the components are simulated. We propose an adaptive rule for this order that reduces the skewness of the weights in numerical examples.

关键词： maximum entropy graph simulation max-min probabilities exponential families

来源：评论

学校读者我要写书评

暂无评论

A Vertex-Centric graph simulation Algorithm for Large graphs

A Vertex-Centric Graph Simulation Algorithm for Large Graphs

引用

第六届中国计算机学会大数据学术会议

作者： Jingdong Li Jin Li Xiaoling Wang Shanghai Key Laboratory of Trustworthy Computing East China Normal University ShanghaiChina School of Software Yunnan University650000 KunmingChina

graph simulation as a well studied model of graph pattern matching problem,has been adopted to reduce the complexity and meet the need of novel applications such as mining potential associations between users in online social *** recent years,graph processing frameworks such as Pregel bring in a vertex-centric,Bulk Synchronous Parallel(BSP)programming model for processing massive data graphs and achieve encouraging ***,developing efficient vertexcentric algorithms for graph simulation model is very challenging,because this problem does not naturally align with a vertex-centric programming *** paper presents novel distributed algorithms based on the vertex-centric programming model for graph *** the same time,considering the enormous cost of the message passing and the algorithm complexity of the pattern matching in the processing of the massive data graph,the part of message passing in the algorithm is optimized to reduce the communication *** experimentally verify the effectiveness and efficiency of these algorithms,using real-life massive data graph.

关键词： vertex-centric graph simulation optimization

来源：评论

学校读者我要写书评

暂无评论

Distributed Partial simulation for graph Pattern Matching

引用

COMPUTER JOURNAL 2024年第1期67卷 110-126页

作者： Aouar, Aissam Yahiaoui, Said Sadeg, Lamia Nouali-Taboudjemat, Nadia Beghdad Bey, Kadda Ecole Mil Polytech BP 17 Algiers 16111 Algeria CERIST Res Ctr Sci & Tech Informat Algiers 16030 Algeria

Pattern matching in big graphs is important for different modern applications. Recently, this problem was defined in terms of multiple extensions of graph simulation, to reduce complexity and capture more meaningful results. These results were achieved through the relaxation of commonly used constraint in subgraph isomorphism pattern matching. Nevertheless, these graph simulation variant models are still too strict to provide results in many cases, especially when analyzed graphs contain anomalies and incomplete information. To deal with this issue, we introduce a new graph pattern matching (GPM) method, called partial simulation, capable of retrieving matches despite missing parts of the pattern graph, such as vertices and/or edges. Furthermore, considering the number and inequality of the outputs, we define a relevance function to compute a value expressing how each match vertex respects the pattern graph. Similarly, we define partial dual simulation GPM that returns vertices that satisfy a part of the dual simulation constraints and assigns a relevance value to them. Additionally, we provide distributed scalable algorithms to evaluate the proposed partial simulation methods based on the distributed vertex-centric programming paradigm. Finally, our experiments on real-world data graphs demonstrate the effectiveness of the proposed models and the efficiency of their associated algorithms.

关键词： big graphs graph pattern matching graph simulation distributed computing vertex-centric programming

来源：评论

学校读者我要写书评

暂无评论

Distributed graph pattern matching via bounded dual simulation

引用

INFORMATION SCIENCES 2022年 610卷 549-570页

作者： Bouhenni, Sarra Yahiaoui, Said Nouali-Taboudjemat, Nadia Kheddouci, Hamamache Ecole Natl Super Informat BP M68 Oued Smar 16309 Algeria Ctr Rech Informat Scientif & Tech CERIST Ben Aknoun 16030 Algeria Univ Lyon 1 Univ Lyon CNRS LIRISUMR5205 F-69622 Villeurbanne France

graph Pattern Matching (GPM) finds subgraphs of a large data graph that are similar to an input query graph. It has many applications, such as pattern recognition, detecting plagia-rism, and finding communities in social networks. Current real-world applications gener-ate massive amounts of data that cannot be stored on the memory of a single machine, which raises the need for distributed storage and processing. Recent relaxed GPM models, although of polynomial time complexity, are nevertheless not distributed by nature. Moreover, the existing relaxed GPM algorithms are limited in terms of scalability. In this paper, we propose Bounded Dual simulation (BDSim) as a new relaxed model for a scalable evaluation of GPM in massive graphs. BDSim captures more semantic similarities com-pared to graph simulation, dual simulation, and even strong simulation. It preserves the vertices' proximity by eliminating cycles of unbounded length from the resulting match graph. Furthermore, we propose distributed vertex-centric algorithms to evaluate BDSim. We prove their effectiveness and efficiency through detailed theoretical validation and extensive experiments conducted on real-world and synthetic datasets. To the best of our knowledge, BDSim is the first relaxed GPM model that captures the cyclic structure of the query graph while being feasible in cubic time. (c) 2022 Elsevier Inc. All rights reserved.

关键词： graph pattern matching Subgraph matching Massive graphs graph simulation Distributed graph processing

来源：评论

学校读者我要写书评

暂无评论

Personalized graph pattern matching via limited simulation

引用

KNOWLEDGE-BASED SYSTEMS 2018年第Feb.1期141卷 31-43页

作者： Du, Ruihuan Yang, Jiannan Cao, Yongzhi Wang, Hanpin Peking Univ Sch Elect Engn & Comp Sci Key Lab High Confidence Software Technol MOE Beijing 100871 Peoples R China

It is well known that graph simulation and bisimulation can capture the semantics of graphs, described by the type and attribute of the nodes and edges. graph pattern matching via simulation has been widely used in a variety of applications such as social network. Recently, some works have investigated the personality of graph simulation. Intuitively, the personality allows each node or edge to have different strengths of matching conditions, which. are typically restricted by the similarity of nodes or edges in graphs. Motivated by the notion of k-limited bisimilarity, which was proposed by Milner to measure the similarity of nodes in the neighbouring subgraphs, and some examples in practice, we employ the notion of k-limited similarity, a weaker version of k-limited bisimilarity, to revisit graph pattern matching in this paper. After establishing the framework for the graph pattern matching via limited simulation, we give an efficient algorithm to compute the maximum match for limited simulation and analyze its computational complexity. To evaluate the algorithm, a group of experiments are conducted for limited simulation and graph simulation. As an extension of limited simulation, we also consider the notion of limited bisimulation for graph pattern matching, and unfortunately, we find that the graph pattern matching via limited bisimulation is NP-hard. (C) 2017 Elsevier B.V. All rights reserved.

关键词： graph pattern matching graph simulation Limited simulation Limited bisimulation

来源：评论

学校读者我要写书评

暂无评论

Fast Dual simulation Processing of graph Database Queries 35

Fast Dual Simulation Processing of Graph Database Queries

引用

IEEE 35th International Conference on Data Engineering (ICDE)

作者： Mennicke, Stephan Kalo, Jan-Christoph Nagel, Denis Kroll, Hermann Balke, Wolf-Tilo TU Braunschweig Inst Informat Syst Braunschweig Germany

ISBN: (纸本)9781538674741

graph database query languages feature expressive yet computationally expensive pattern matching capabilities. Answering optional query clauses in SPARQL for instance renders the query evaluation problem immediately PSPACE-complete. Light-weight graph pattern matching relations, such as simulation, have recently been investigated as promising alternatives to more expensive query mechanisms like, e.g., computing subgraph isomorphism. Still, pattern matching alone lacks expressive query capabilities: graph patterns may be combined by usual inner joins. However, including more sophisticated operators is inevitable to make solutions more useful for emerging applications. In this paper we bridge this gap by introducing a new dual simulation process operating on SPARQL queries. In addition to supporting the full syntactic structure of SPARQL queries, it features polynomial-time pattern matching to compute an overapproximation of the query results. Moreover, to achieve running times competing with state-of-the-art database systems, we develop a novel algorithmic solution to dual simulation graph pattern matching, based on a system of inequalities that allows for several optimization heuristics. Finally, we achieve soundness of our process for SPARQL queries including UNION, AND and OPTIONAL operators not restricted to well-designed patterns. Our experiments on synthetic and real-world graph data promise a clear gain for graph database systems when incorporating the new dual simulation techniques.

关键词： graph databases query processing graph simulation SPARQL

来源：评论

学校读者我要写书评

暂无评论

Strong simulation: Capturing Topology in graph Pattern Matching

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2014年第1期39卷 4-4页

作者： Ma, Shuai Cao, Yang Fan, Wenfei Huai, Jinpeng Wo, Tianyu Beihang Univ Sch Comp Sci & Engn Beijing Peoples R China Beihang Univ SKLSDE Lab Beijing Peoples R China Univ Edinburgh Lab Fdn Comp Sci Sch Informat Informat Forum Edinburgh EH8 9AB Midlothian Scotland

graph pattern matching is finding all matches in a data graph for a given pattern graph and is often defined in terms of subgraph isomorphism, an NP-complete problem. To lower its complexity, various extensions of graph simulation have been considered instead. These extensions allow graph pattern matching to be conducted in cubic time. However, they fall short of capturing the topology of data graphs, that is, graphs may have a structure drastically different from pattern graphs they match, and the matches found are often too large to understand and analyze. To rectify these problems, this article proposes a notion of strong simulation, a revision of graph simulation for graph pattern matching. (1) We identify a set of criteria for preserving the topology of graphs matched. We show that strong simulation preserves the topology of data graphs and finds a bounded number of matches. (2) We show that strong simulation retains the same complexity as earlier extensions of graph simulation by providing a cubic-time algorithm for computing strong simulation. (3) We present the locality property of strong simulation which allows us to develop an effective distributed algorithm to conduct graph pattern matching on distributed graphs. (4) We experimentally verify the effectiveness and efficiency of these algorithms using both real-life and synthetic data.

关键词： Algorithms Experimentation Performance Theory Strong simulation dual simulation graph simulation subgraph isomorphism data locality

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：