Search

In Distributed Database System (DBS) and multitasking system, the occurrence of deadlocks is one of the most serious problems. If a site request for a resource that is already in the another site which is waiting for another resource then the scenario is called as distributed deadlock. Different distributed environments require a suitable deadlock detection algorithm to detect deadlocks. Different distributed environments needs to maintain their platforms by avoiding deadlocks. To achieve this environment, it is required to fed with optimized deadlock detection and avoidance algorithms. In this article, different deadlock detection algorithms that uses Wait For Graph and resolution algorithms to trace out deadlocks were discussed. An optimization technique is used for resolving deadlock in an efficient manner. A comparison between different deadlock detection algorithms based on different parameters like, delay time, message size, number of messages and whether the algorithm detects false deadlocks or not were performed. Based on the comparisons, a few deadlock detection algorithms were suggested for the distributed environment.

A social network can be defined as a complex graph, which is a collection of nodes connected via edges. Nodes represent individual actors or people in the network, whereas edges define relationships among those actors. Most popular social networks are Facebook, Twitter, and Google+. To analyze these social networks, one needs specialized tools for analysis. This chapter presents a comparative study of such tools based on the general graph aspects as well as the social network mining aspects. While considering the general graph aspects, this chapter presents a comparative study of four social network analysis tools—NetworkX, Gephi, Pajek, and IGraph—based on the platform, execution time, graph types, algorithm complexity, input file format, and graph features. On the basis of the social network mining aspects, the chapter provides a comparative study on five specialized tools—Weka, NetMiner 4, RapidMiner, KNIME, and R—with respect to the supported mining tasks, main functionality, acceptable input formats, output formats, and platform used.

In distributed system, a single database is spread physically across computers in multiple locations called distributed database. One of the most serious problems in distributed database is deadlock. The deadlock is a state of the system in which transactions are waiting for one another indefinitely. This paper presents a new algorithm to detect multi resource deadlocks using directed graph. The proposed algorithm is development over the algorithms by Brain M. Johnston and Himanshi Grover. In previous algorithms, there is no criteria to decide the transaction, which needs to be aborted early to reduce the repeated time of detections. It makes this decision using incoming and out coming requests of transactions in graph as criteria to decide such transaction to detected and aborted early. It ensures that only one transaction will detect the deadlock cycle. All true deadlocks are detected in finite time and no false and undetected deadlocks are reported.

We reduce the cost of communication and synchronization in graph processing by analyzing the fastest way to process graphs: pushing the updates to a shared state or pulling the updates to a private state. We investigate the applicability of this push-pull dichotomy to various algorithms and its impact on complexity, performance, and the amount of used locks, atomics, and reads/writes. We consider 11 graph algorithms, 3 programming models, 2 graph abstractions, and various families of graphs. The conducted analysis illustrates surprising differences between push and pull variants of different algorithms in performance, speed of convergence, and code complexity; the insights are backed up by performance data from hardware counters. We use these findings to illustrate which variant is faster for each algorithm and to develop generic strategies that enable even higher speedups. Our insights can be used to accelerate graph processing engines or libraries on both massively-parallel shared-memory machines as well as distributed-memory systems.

Recently, people, devices, processes, and other entities have been more connected than at any other point in history. In general, a graph is a natural, neat, and flexible structure to model the complex relationships, interactions, and interdependencies between objects (Fig. 4.1). In particular, each graph consists of nodes (or vertices) that represent objects and edges (or links) that represent the relationships among the graph nodes. Graphs have been widely used to represent datasets in a wide range of application domains such as social science, astronomy, computational biology, telecommunications, computer networks, semantic Web, protein networks, and many others (Sakr and Pardede, Graph Data Management: Techniques and Applications, 2011 [73]).

Although graph databases have great potential to directly represent huge and complex network structures, such as social and logistics networks, they currently do not perform well enough. To achieve a two-orders-of-magnitude performance improvement on graph database queries, the authors propose caching the graph database in distributed GPUs connected with a 10-Gbit Ethernet (10GbE) network. Property read, traverse, and graph search queries are accelerated by 25.9, 252.4, and 383.2 times, respectively, compared to those using Neo4j for a huge graph consisting of 3.2 million nodes whose degree is 100.

While developing concurrent systems, one of the important properties to be checked is deadlock freedom. Model checking is an accurate technique to detect errors, such as deadlocks. However, the problem of model checking in complex software systems is state space explosion in which all reachable states cannot be generated due to exponential memory usage. When a state space is too large to be explored exhaustively, using meta-heuristic and evolutionary approaches seems a proper solution to address this problem. Recently, a few methods using genetic algorithm, particle swarm optimization and similar approaches have been proposed to handle this problem. Even though the results of recent approaches are promising, the accuracy and convergence speed may still be a problem. In this paper, a novel method is proposed using Bayesian Optimization Algorithm (BOA) to detect deadlocks in systems specified formally through graph transformations. BOA is an Estimation of Distribution Algorithm in which a Bayesian network (as a probabilistic model) is learned from the population and then sampled to generate new solutions. Three different structures are considered for the Bayesian network to investigate deadlocks in the benchmark problems. To evaluate the efficiency of the proposed approach, it is implemented in GROOVE, an open source toolset for designing and model checking graph transformation systems. Experimental results show that the proposed approach is faster and more accurate than existing algorithms in discovering deadlock states in the most of case studies with large state spaces.

In this paper, we propose ExtraV, a framework for near-storage graph processing. It is based on the novel concept of graph virtualization , which efficiently utilizes a cache-coherent hardware accelerator at the storage side to achieve performance and flexibility at the same time. ExtraV consists of four main components: 1) host processor, 2) main memory, 3) AFU (Accelerator Function Unit) and 4) storage. The AFU, a hardware accelerator, sits between the host processor and storage. Using a coherent interface that allows main memory accesses, it performs graph traversal functions that are common to various algorithms while the program running on the host processor (called the host program) manages the overall execution along with more application-specific tasks. Graph virtualization is a high-level programming model of graph processing that allows designers to focus on algorithm-specific functions. Realized by the accelerator, graph virtualization gives the host programs an illusion that the graph data reside on the main memory in a layout that fits with the memory access behavior of host programs even though the graph data are actually stored in a multi-level, compressed form in storage. We prototyped ExtraV on a Power8 machine with a CAPI-enabled FPGA. Our experiments on a real system prototype offer significant speedup compared to state-of-the-art software only implementations.

This paper studies algorithmic aspects of deadlock analysis for parameterized networks of discrete-event systems. A parameterized network consists of interacting finite-state subsystems, including finite but arbitrarily large numbers of subsystems within each of a finite number of isomorphism classes. While deadlock analysis of such systems is generally undecidable, decidable subproblems have recently been identified. The decision procedure of Zibaeenejad and Thistle (2017) rests on the construction of a finite dependency graph for the network, and the computation of its full, consistent subgraphs. We present a software tool that takes the template of a Parameterized Chain Network (PCN) and outputs the set of all full, consistent subgraphs of the dependency graph. These subgraphs represent infinite set of deadlocked states of the PCN for all parameter values. As a case study, we investigate deadlock in a complex train network that extends beyond the current theoretical framework. The results suggest ways in which the framework could be extended.

Driven by a multitude of use cases, graph data analytics has become a hot topic in research and industry. Particularly on big graphs, performing complex analytical queries efficiently to derive new insights is a challenging task. Systems that aim at solving the technical part of this challenge are often referred to as graph processing systems. They allow expressing and executing analytic algorithms and queries, while hiding most of the technical details related to efficiently storing and processing graph data. Since 2010, work on graph processing systems for distributed systems as well as shared memory systems has virtually exploded. In this article, we give an overview of this work with the particular focus on graph processing systems for large multiprocessor machines. We describe the state of the art established in recent years and outline trends and challenges in research and development that point towards the future of graph processing systems.

This paper investigates sign-consensus problems of general linear multi-agent systems. The interaction between agents is modeled by a signed directed graph, where both cooperation and competition coexist within a group. The graph is allowed to be structurally unbalanced and its adjacency matrix is assumed to be eventually positive. Distributed control laws are proposed for several classes of graph topologies. Simulation examples are provided to illustrate the proposed control laws. Signed graph-based multi-agent systems provide models to opinion dynamics and social networks, and may also hold significance in further developing such internet search algorithms as PageRank to counter spamming websites.

Comparing graph databases with traditional,e.g., relational databases, some important database features are often missing there. Particularly, a graph database schema including integrity constraints is mostly not explicitly defined, also a conceptual modelling is not used. It is hard to check a consistency of the graph database, because almost no integrity constraints are defined or only their very simple representatives can be specified. In the paper, we discuss these issues and present current possibilities and challenges in graph database modelling. We focus also on integrity constraints modelling and propose functional dependencies between entity types, which reminds modelling functional dependencies known from relational databases. We show a number of examples of often cited GDBMSs and their approach to database schemas and ICs specification. Also a conceptual level of a graph database design is considered. We propose a sufficient conceptual model based on a binary variant of the ER model and show its relationship to a graph database model, i.e. a mapping conceptual schemas to database schemas. An alternative based on the conceptual functions called attributes is presented. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

In recent year, many large-scale iterative graph computation systems such as Pregel have been developed. To ensure that these systems are fault-tolerant, checkpointing, which archives graph states onto distributed file systems periodically, has been proposed. However, fault-tolerance remains to be challenging because the whole data set is archived with a static interval, rendering underlying graph computations to entail I/O-costs in terms of disk and network communication. Motivated by this, we first propose to dynamically adjust checkpoint intervals based on a carefully designed cost-analysis model, by taking the underlying computing workload into account. Furthermore, for algorithms that can be restarted from any point during computations, we prioritize graph states and then checkpointing can be performed with selected data, instead of the entire dataset, to reduce archiving overhead while simultaneously guaranteeing the failure recovery efficiency. Finally, we conduct extensive performance studies to confirm the effectiveness of our approaches over existing up-to-date solutions using a broad spectrum of real-world graphs.

International audience; NoSQL graph databases have been introduced in recent years for dealing with large collections of graph-based data. Scientific data and social networks are among the best examples of the dramatic increase of the use of such structures. NoSQL repositories allow the management of large amounts of data in order to store and query them. Such data are not structured with a predefined schema as relational databases could be. They are rather composed by nodes and relationships of a certain type. For instance, a node can represent a Person and a relationship Friendship. Retrieving the structure of the graph database is thus of great help to users, for example when they must know how to query the data or to identify relevant data sources for recommender systems. For this reason, this paper introduces methods to retrieve structural summaries. Such structural summaries are extracted at different levels of information from the NoSQL graph database. The expression of the mining queries is facilitated by the use of two frame-works: Fuzzy4S allowing to define fuzzy operators and operations with Scala; Cypherf allowing the use of fuzzy operators and operations in the declarative queries over NoSQL graph databases. We show that extracting such summaries can be impossible with the NoSQL query engines because of the data volume and the complexity of the task of automatic knowledge extraction. A novel method based on in memory architectures is thus introduced. This paper provides the definitions of the summaries with the methods to automatically extract them from NoSQL graph databases only and with the help of in-memory architectures. The benefit of our proposition is demonstrated by experimental results.

Graph processing is becoming a crucial component for analyzing big data arising in many application domains such as social and biological networks, fraud detection, and sentiment analysis. As a result, a number of computational models for graph analytics have been proposed in the literature to help users write efficient large scale graph algorithms. In this paper we present an alternative model for implementing graph algorithms using a linear algebra based specification. We first specify a set of linear algebra primitives that allows users to express graph algorithms by composition of linear algebra operations. We then describe a high performance implementation of these primitives using C $$++$$ and subsequently its integration with the Spark framework to achieve the scalability we need for large systems. We provide an overview of our implementation and also compare and contrast the expressiveness and performance of various algorithms implemented with our approach with that of the current Spark GraphX implementation of those algorithms.

We are witnessing an enormous growth in social networks as well as in the volume of data generated by them. An important portion of this data is in the form of graphs. In recent years, several graph processing and management systems emerged to handle large-scale graphs. The primary goal of these systems is to run graph algorithms and queries in an efficient and scalable manner. Unlike relational data, graphs are semi-structured in nature. Thus, storing and accessing graph data using secondary storage requires new solutions that can provide locality of access for graph processing workloads. In this work, we propose a scalable block formation and layout technique for graphs, which aims at reducing the I/O cost of disk-based graph processing algorithms. To achieve this, we designed a scalable MapReduce-style method called ICBL, which can divide the graph into a series of disk blocks that contain sub-graphs with high locality. Furthermore, ICBL can order the resulting blocks on disk to further reduce non-local accesses. We experimentally evaluated ICBL to showcase its scalability, layout quality, as well as the effectiveness of automatic parameter tuning for ICBL. We deployed the graph layouts generated by ICBL on the Neo4j open source graph database, http://www.neo4j.org/ (2015) graph database management system. Our results show that the layout generated by ICBL reduces the query running times over Neo4j more than 2 × compared to the default layout. © 2017, Springer Science+Business Media New York.

One thing that is still being developed for graph databases is integrity constraint (IC) support. One possibility to IC proposal is to consider a graph conceptual schema and a graph database schema. At least inherent ICs coming from a graph conceptual schema should be considered as explicit ICs on the graph databases level, i.e., using a DDL. In the paper, we focus on graph database Neo4j and its possibilities to express a database schema and ICs. We extend these possibilities through new constructs in Neo4j DDL including their prototype implementation and experiments.

Rich metadata in high-performance computing (HPC) systems contains extended information about users, jobs, data files, and their relationships. Property graphs are a promising data model to represent heterogeneous rich metadata flexibly. Specifically, a property graph can use vertices to represent different entities and edges to record the relationships between vertices with unique annotations. The high-volume HPC use case, with millions of entities and relationships, naturally requires an out-of-core distributed property graph database, which must support live updates (to ingest production information in real time), low-latency point queries (for frequent metadata operations such as permission checking), and large-scale traversals (for provenance data mining).Among these needs, large-scale property graph traversals are particularly challenging for distributed graph storage systems. Most existing graph systems implement a "level-synchronous" breadth-first search algorithm that relies on global synchronization in each traversal step. This performs well in many problem domains; but a rich metadata management system is characterized by imbalanced graphs, long traversal lengths, and concurrent workloads, each of which has the potential to introduce or exacerbate stragglers (i.e., abnormally slow steps or servers in a graph traversal) that lead to low overall throughput for synchronous traversal algorithms. Previous research indicated that the straggler problem can be mitigated by using asynchronous traversal algorithms, and many graph-processing frameworks have successfully demonstrated this approach. Such systems require the graph to be loaded into a separate batch-processing framework instead of being iteratively accessed, however.In this work, we investigate a general asynchronous graph traversal engine that can operate atop a rich metadata graph in its native format. We outline a traversal-aware query language and key optimizations (traversal-affiliate caching and execution merging) necessary for efficient performance. We further explore the effect of different graph partitioning strategies on the traversal performance for both synchronous and asynchronous traversal engines. Our experiments show that the asynchronous graph traversal engine is more efficient than its synchronous counterpart in the case of HPC rich metadata processing, where more servers are involved and larger traversals are needed. Moreover, the asynchronous traversal engine is more adaptive to different graph partitioning strategies.

Recently graph has been drawing lots of attention both as a natural data model that captures fine-grained relationships between data entities and as a tool for powerful data analysis that considers such relationships. In this paper, we present a new graph database system that integrates a robust graph storage with an efficient graph analytics engine. Primarily, our system adopts two domain-specific languages (DSLs), one for describing graph analysis algorithms and the other for graph pattern matching queries. Compared to the API-based approaches in conventional graph processing systems, the DSL-based approach provides users with more flexible and intuitive ways of expressing algorithms and queries. Moreover, the DSL-based approach has significant performance benefits as well, (1) by skipping (remote) API invocation overhead and (2) by applying high-level optimization from the compiler.

The pervasiveness of graphs on the Web is growing; however, the difficulty of managing complex graph structures curbs the development of web-oriented applications that embed network data. The open source project, L evel G raph , aims to overcome the obstacles that web developers face with graph data management. L evel G raph is an easy-to-use graph database layer for web applications. To demonstrate various capabilities of the system, we developed a web-based application that utilizes a graph database of a tourist network in New Delhi. The application allows users to move around the city while L evel G raph executes graph queries on the underlying database. In this demonstration, we show how L evel G raph 's features facilitate development and maintainance of web applications that embed graph data.

A lot of real-life data are of graph nature. However, it is not until recently that business begins to exploit data's connectedness for business insights. On the other hand, RDBMSs are a mature technology for data management, but they are not for graph processing. Take graph traversal, a common graph operation for example, it heavily relies on a graph primitive that accesses a given node's neighborhood. We need to join tables following foreign keys to access the nodes in the neighborhood if an RDBMS is used to manage graph data. Graph exploration is a fundamental building block of many graph algorithms. But this simple operation is costly due to a large volume of I/O caused by the massive amount of table joins. In this paper, we present G-SQL, our effort toward the integration of a RDBMS and a native in-memory graph processing engine. G-SQL leverages the fast graph exploration capability provided by the graph engine to answer multi-way join queries. Meanwhile, it uses RDBMSs to provide mature data management functionalities, such as reliable data storage and additional data access methods. Specifically, G-SQL is a SQL dialect augmented with graph exploration functionalities and it dispatches query tasks to the in-memory graph engine and its underlying RDMBS. The G-SQL runtime coordinates the two query processors via a unified cost model to ensure the entire query is processed efficiently. Experimental results show that our approach greatly expands capabilities of RDBMs and delivers exceptional performance for SQL-graph hybrid queries.

The efficient visualization of dynamic network structures has become a dominant problem in many big data applications, such as large network analytics, traffic management, resource allocation graphs, logistics, social networks, and large document repositories. In this paper, we present a large-graph visualization system called ModuleGraph. ModuleGraph is a scalable representation of graph structures by treating a graph as a set of modules. The main objectives are: (1) to detect graph patterns in the visualization of large-graph data, and (2) to emphasize the interconnecting structures to detect potential interactions between local modules. Our first contribution is a hybrid modularity measure. This measure partitions the cohesion of the graph at various levels of details. We aggregate clusters of nodes and edges into several modules to reduce the overlap between graph components on a 2D display. Our second contribution is a k-clustering method that can flexibly detect the local patterns or substructures in modules. Patterns of modules are preserved by the ModuleGraph system to avoid information loss, while sub-graphs are clustered as a single node. Our experiments show that this method can efficiently support large-scale social and spatial network visualization. Graphical Abstract text

A large number of specialized graph processing systems have been developed to cope with the increasing demand of graph analytics. Most of them require users to deploy a new framework in the cluster for graph processing and switch to other systems to execute non-graph algorithms. This increases the complexity of cluster management and results in unnecessary data movement and duplication. In this paper, we propose our graph processing engine, named epiCG, which is built on top of epiC, an elastic data processing system. The core of epiCG is a new unit called GraphUnit, which is able to not only perform iterative graph processing efficiently, but also collaborate with other types of units to accomplish any complex/multi-stage data analytics. epiCG supports both edge-cut and vertex-cut partitioning methods, and for the latter method, we propose a novel light-weight greedy strategy that enables all the GraphUnits to generate vertex-cut partitioning in parallel. Furthermore, unlike existing graph processing systems, failure recovery in epiCG is completely automatic. We compare epiCG with several prevalent graph processing systems via extensive experiments with real-life dataset and applications. The results show that epiCG possesses high efficiency and scalability, and performs exceptionally well in large dataset settings, showcasing its suitability for large-scale graph processing.

With the popularity of social network, the demand for real-time processing of graph data is increasing. However, most of the existing graph systems adopt a batch processing mode, therefore the overhead of maintaining and processing of dynamic graph is significantly high. In this paper, we design iGraph, an incremental graph processing system for dynamic graph with its continuous updates. The contributions of iGraph include: 1) a hash-based graph partition strategy to enable fine-grained graph updates; 2) a vertexbased graph computing model to support incremental data processing; 3) detection and rebalance methods of hotspot to address the workload imbalance problem during incremental processing. Through the general-purpose API, iGraph can be used to implement various graph processing algorithms such as PageRank. We have implemented iGraph on Apache Spark, and experimental results show that for real life datasets, iGraph outperforms the original GraphX in respect of graph update and graph computation.

We present implementations of six popular graph mining algorithms using SPARQL.We present guidelines for efficient graph mining algorithms using SPARQL.We released our implementation as publicly available open-source project.We analyzed the performance of our implementation on various system environments. Graph analysis is now considered as a promising technique to discover useful knowledge from data. We posit that there are two dimensions of graph analysis: OnLine Graph Analytic Processing (OLGAP) and Graph Mining (GM) where each respectively focuses on subgraph pattern matching and automatic knowledge discovery. As these two dimensions aim to complementarily solve complex problems, holistic in-situ graph analysis which covers both OLGAP and GM in a single system is critical for minimizing the burdens of operating multiple graph systems and transferring intermediate result-sets between those systems. Nevertheless, most existing graph analysis systems are only capable of one dimension of graph analysis. In this work, we take an approach to enabling GM capabilities (e.g., PageRank, connected-component analysis, node eccentricity, etc.) in RDF triplestores, which are originally developed to store RDF datasets and provide OLGAP capability. More specifically, to achieve our goal, we implemented six representative graph mining algorithms using SPARQL. The approach allows a wide range of available RDF datasets directly applicable for holistic graph analysis within a system. For validation of our approach, we evaluate performance of our implementations with nine real-world datasets and three different computing environments - a laptop computer, an Amazon EC2 instance, and a shared-memory Cray XMT2 URIKA-GD graph-processing appliance. The experimental results show that our implementation can provide promising and scalable performance for real world graph analysis in all tested environments. The developed software is publicly available in an open-source project that we initiated.

In this brief, we consider the consensus problem of a switched multiagent system composed of continuous-time (CT) and discrete-time (DT) subsystems. By combining the classical consensus protocols of CT and DT multiagent systems, we propose a linear consensus protocol for switched multiagent system. Based on the graph theory and the Lyapunov theory, we prove that the consensus of switched multiagent system is solvable under arbitrary switching with undirected connected graph, directed graph, and switching topologies, respectively. Simulation examples are also provided to demonstrate the effectiveness of the theoretical results.

Pioneered by Google's Pregel, many distributed systems have been developed for large-scale graph analytics. These systems employ a user-friendly "think like a vertex" programming model, and exhibit good scalability for tasks where the majority of graph vertices participate in computation. However, the design of these systems can seriously under-utilize the resources in a cluster for processing light-workload graph queries, where only a small fraction of vertices need to be accessed. In this work, we develop a new open-source system, called Quegel , for querying big graphs. Quegel treats queries as first-class citizens in its design: users only need to specify the Pregel-like algorithm for a generic query, and Quegel processes light-workload graph queries on demand, using a novel superstep-sharing execution model to effectively utilize the cluster resources. Quegel further provides a convenient interface for constructing graph indexes, which significantly improve query performance but are not supported by existing graph-parallel systems. Our experiments verified that Quegel is highly efficient in answering various types of graph queries and is up to orders of magnitude faster than existing systems.

Deadlock Avoidance remains to be a significant aspect of deadlock research. Modeling approaches based on Graph Theory provide effective strategy to solve this problem. We built avoidance model of directed graph and adjacent matrix via resource allocation graph, proposed three improved algorithm for deadlock avoidance and discussed the implementation of the program. The topology analyze of matrix storage information indicates entire optimization utilization results though certain key vertices and edges, this model verified by the banker’s algorithm and Petri net finally.

Intelligent systems of processing and representing the knowledge are presently developed towards the integration of symbol and image representations of scientific knowledge. In combination with well-developed hardware and software multimedia tools this trend in engineering of science has a great practical importance especially at the stage of conversion of paper documents into their electronic equivalents. In this situation there occur some problems related to the form of representation of knowledge, configuration of user interfaces, recognition of the input information and providing for high speed of its search and processing.

The world of system of systems engineering (SoSE), and consequently systems engineering, is currently being reformalized so as to provide greater functionality, integration, and extensibility into designed systems of systems (SoS). Graph theory and big data techniques are in position to play substantial roles in this reformalization, and hence, this paper fills a significant need by bringing together all known current applications of graph theory to SoSE in tutorial/summary form. In this paper, we explore the applications of graph theory and known graph algorithms for system design (and SoS design), optimization techniques, complexity measures, and novel graph algorithms for real-time deployment of SoS’s and managing SoS design. The work is straightforward with several examples, and is meant to be a standalone document that can be used to quickly come up to speed regarding the applications of graph theory in SoSE.

Graph databases can be defined as databases that use graph structures with nodes, edges and properties to store data. Semantic queries and graph-oriented operations are used to access them. With a rapidly growing amount of information on the Internet in recent years, relational databases suffer performance degradation as a large number of nodes are added due to the number of entries in join tables. Therefore, based on the network nature of Internet activities, graph databases are designed for fast access to complex data found in social networks, recommendation engines and networked system. The main objective of this survey is to present the work that has been done in the area of graph database, including query languages, processing, and related application.

Today, software has become an intrinsic part of complex distributed embedded real-time systems. The next generation of embedded real-time systems will interconnect the today unconnected systems via complex software parts and the service-oriented paradigm. Due to these interconnections, the architecture of systems can be subject to changes at run-time, e.g. when dynamic binding of service end-points is employed or complex collaborations are established dynamically. However, suitable formalisms and techniques that allow for modeling and analysis of timed and probabilistic behavior of such systems as well as of their structure dynamics do not exist so far. To fill the identified gap, we propose Probabilistic Timed Graph Transformation Systems (PTGTSs) as a high-level description language that supports all the necessary aspects of structure dynamics, timed behavior, and probabilistic behavior. We introduce the formal model of PTGTSs in this paper as well as present and formally verify a mapping of models with finite state spaces to probabilistic timed automata (PTA) that allows to use the PRISM model checker to analyze PTGTS models with respect to PTCTL properties. (C) 2018 Elsevier Inc. All rights reserved.

The vertex-centric programming model is an established computational paradigm recently incorporated into distributed processing frameworks to address challenges in large-scale graph processing. Billion-node graphs that exceed the memory capacity of commodity machines are not well supported by popular Big Data tools like MapReduce, which are notoriously poor performing for iterative graph algorithms such as PageRank. In response, a new type of framework challenges one to “think like a vertex” (TLAV) and implements user-defined programs from the perspective of a vertex rather than a graph. Such an approach improves locality, demonstrates linear scalability, and provides a natural way to express and compute many iterative graph algorithms. These frameworks are simple to program and widely applicable but, like an operating system, are composed of several intricate, interdependent components, of which a thorough understanding is necessary in order to elicit top performance at scale. To this end, the first comprehensive survey of TLAV frameworks is presented. In this survey, the vertex-centric approach to graph processing is overviewed, TLAV frameworks are deconstructed into four main components and respectively analyzed, and TLAV implementations are reviewed and categorized.

Graph data management and matching similar graphs are very important for many applications including bioinformatics, computer vision, VLSI design, bug localization, road networks, social and communication networking. Many graph indexing and similarity matching techniques have already been proposed for managing and querying graph data. In similar graph matching, a user is returned with the database graphs whose distances with the query graph are below a threshold. In such query settings, a user may not receive certain database graphs that are very similar to the query graph if the initial query graph is inappropriate/imperfect for the expected answer set. To exemplify this, consider a drug designer who is looking for chemical compounds that could be the target of her hypothetical drug before realizing it. In response to her query, the traditional search system may return the structures from the database that are most similar to the query graph. However, she may get surprised if some of the expected targets are missing in the answer set. She may then seek assistance from the system by asking “Is there other query graph that can match my expected answer set?”. The system may then modify her initial query graph to include the missing answers in the new answer set. Here, we study this kind of problem of answering why-not questions in similar graph matching for graph databases.

Analyzing interconnection structures among the data through the use of graph algorithms and graph analytics has been shown to provide tremendous value in many application domains. However, graphs are not the primary choice for how most data is currently stored, and users who want to employ graph analytics are forced to extract data from their data stores, construct the requisite graphs, and then use a specialized engine to write and execute their graph analysis tasks. This cumbersome and costly process not only raises barriers in using graph analytics, but also makes it hard to explore and identify hidden or implicit graphs in the data. Here we demonstrate a system, called G raph G en , that enables users to declaratively specify graph extraction tasks over relational databases, visually explore the extracted graphs, and write and execute graph algorithms over them, either directly or using existing graph libraries like the widely used NetworkX Python library. We also demonstrate how unifying the extraction tasks and the graph algorithms enables significant optimizations that would not be possible otherwise.

Graph transformation is an important modeling and analysis technique widely applied in software engineering. The attributes can naturally conceptualize the properties of the modeled artifacts. However, the lack of support for the specification of such attribute correspondence by ordinary propositional temporal logics hampers its further application during verification. Different from the theoretical investigations on quantified second order logics, we propose a practical and light-weight approach for the verification of this kind of temporal specifications with associated attributes. Particularly, we apply our approach and extend the generalpurpose graph transformation modeling tool: Groove. Moreover, symmetry reduction techniques are exploited to reduce the number of states. Experiments with performance evaluations complement our discussion and demonstrate the feasibility and efficiency of our approach.

This paper proposes lower bounds for the coupling strengths of oscillators in directed networks to guarantee global synchronization. The novel idea of graph comparison from spectral graph theory is employed so that the combinatorial features of a given network can be fully utilized to simplify computations. For large networks that can be decomposed into a set of smaller strongly connected components, the comparison can be carried out at the local level as well. To validate theoretical analysis, examples are provided to demonstrate how to apply the proposed methodologies to typical directed complex networks.

We present Armus, a verification tool for dynamically detecting or avoiding barrier deadlocks. The core design of Armus is based on phasers, a generalisation of barriers that supports split-phase synchronisation, dynamic membership, and optional-waits. This allows Armus to handle the key barrier synchronisation patterns found in modern languages and libraries. We implement Armus for X10 and Java, giving the first sound and complete barrier deadlock verification tools in these settings. Armus introduces a novel event-based graph model of barrier concurrency constraints that distinguishes task-event and event-task dependencies. Decoupling these two kinds of dependencies facilitates the verification of distributed barriers with dynamic membership, a challenging feature of X10. Further, our base graph representation can be dynamically switched between a task-to-task model, Wait-for Graph (WFG), and an event-to-event model, State Graph (SG), to improve the scalability of the analysis. Formally, we show that the verification is sound and complete with respect to the occurrence of deadlock in our core phaser language, and that switching graph representations preserves the soundness and completeness properties. These results are machine checked with the Coq proof assistant. Practically, we evaluate the runtime overhead of our implementations using three benchmark suites in local and distributed scenarios. Regarding deadlock detection, distributed scenarios show negligible overheads and local scenarios show overheads below 1.15×. Deadlock avoidance is more demanding, and highlights the potential gains from dynamic graph selection. In one benchmark scenario, the runtime overheads vary from 1.8× for dynamic selection, 2.6× for SG-static selection, and 5.9× for WFG-static selection.

The scheduling and mapping of task graph to processors is considered to be the most crucial NP-complete in parallel and distributed computing systems. In this paper, the theoretical graph application using matching is presented to assign a number of tasks onto two processors. This paper addresses a directed-weighted cyclic graph. The effort is to reduce the graph onto directed acyclic graph. A co-comparability graph is presented in order to assign the task onto two processors. Combining several innovative techniques lead to an efficient graph-mapping concept, called DCGSimplify. Our simulation model found that the proposed techniques and algorithms are easy to be implemented.

Existing distributed graph processing frameworks, e.g. , Pregel, Giraph, GPS and GraphLab, mainly exploit main memory to support flexible graph operations for efficiency. Due to the complexity of graph analytics, huge memory space is required especially for those graph analytics that spawn large intermediate results. Existing frameworks may terminate abnormally or degrade performance seriously when the memory is exhausted or the external storage has to be used. In this paper, we propose MOCgraph, a scalable distributed graph processing framework to reduce the memory footprint and improve the scalability, based on message online computing. MOCgraph consumes incoming messages in a streaming manner, so as to handle larger graphs or more complex analytics with the same memory capacity. MOCgraph also exploits message online computing with external storage to provide an efficient out-of-core support. We implement MOCgraph on top of Apache Giraph, and test it against several representative graph algorithms on large graph datasets. Experiments illustrate that MOCgraph is efficient and memory-saving, especially for graph analytics with large intermediate results.

Flexible manufacturing systems exhibit a high degree of resource sharing. Since the parts advancing through the system compete for a finite number of resources, a deadlock may occur. Accordingly, many pioneers make efforts in the issue. However, how to obtain maximally permissive supervisors in deadlock flexible manufacturing system is an extremely difficult and time-consuming problem. In existing literature, place invariant) and graph analysis method are merged called maximal number of forbidding First Bad Marking (FBM) problem to obtained optimal controllers with a small number of control places. However, this prevention just can be used in some special nets. For general cases, deadlocks could still exist. Therefore, this paper tries to propose one improved iterative deadlock prevention policy to solve above disadvantage. Experimental results show that the proposed improved policy can be used in all kinds of nets. In other words, it does improve the drawback of conventional maximal number of forbidding First Bad Marking (FBM) problem technology.

The paper describes the concept of parallel graph processing system, which allows to develop architecture independent applications for processing large graphs. Also, the system allows the user to abstract from the implementation details of the graph storage format. This system can be used in such fast growing research fields as network science.

The rapidly growing number of large network analysis problems has led to the emergence of many parallel and distributed graph processing systems—one survey in 2014 identified over 80. Determining the best approach for a given problem is infeasible for most developers. We present an approach and associated software for analyzing the performance and scalability of parallel, open-source graph libraries. We demonstrate our approach on five graph processing packages: GraphMat, Graph500, Graph Algorithm Platform Benchmark Suite, GraphBIG, and PowerGraph using synthetic and real-world datasets. We examine previously overlooked aspects of parallel graph processing performance such as phases of execution and energy usage for three algorithms: breadth first search, single source shortest paths, and PageRank.