Given a dataset representing the entities and relations among them, performing analysis via representation as a Graph is referred to as Graph Analytics. In a real-time setting, where the dataset is updated at both speed and volume, this problem offers non-trivial challenges along with immense opportunities.
Relevance
A graph represents the pairwise relationships between objects or entities that underlie complex frameworks such as blockchains, social networks, semantic-web, biological networks, and many others. The objects are represented by nodes and the edges in the graph correspond to relationships. Often these applications are implemented on dynamic graphs, i.e. they face the addition and removal of data corresponding to objects and/or relationships. For example, consider the computation of the shortest path or centrality between nodes in a real-time dynamically changing social network. Such settings are challenging and approaches such as incremental computation or streaming framework, where a graph operation is performed over a static temporal snapshot of the data structure are fairly standard.
As multicore CPUs are commonplace now, the dynamic updates via concurrency are natural. However, the application of concurrency in dynamic graph algorithms is largely unexplored where dynamic dataset updates severely hinder parallel operation-processing designed for static graphs. Indeed, concurrent operations substantially speed up the implementation and make it real-time in a practical sense.
Objectives
We explore the following research problems in this domain:
-
Design and Implementation of concurrent dynamic graph data structure.
-
Non-blocking concurrency of data structure operations.
-
Proving correctness (linearizability) of non-blocking graphs.
-
Learned graph queries.
-
Dynamic big graph analytics on graphics processing units (GPUs). –>
Approach
Our real-time graph analytics mainly applies concurrency for running multiple graph algorithms on a single graph simultaneously. This can be done in a number of ways, but the most common approach is to divide the graph into multiple partitions and assign each partition to a different worker node. The worker nodes can then run their respective algorithms on their assigned partitions in parallel.
Concurrent graph analytics has a number of advantages over traditional sequential graph analytics. First, it can significantly improve performance, especially for large and complex graphs. Second, it can make graph processing more scalable, as multiple worker nodes can be used to process the graph in parallel. Third, it can improve fault tolerance, as the failure of a single worker node will not affect the execution of the other worker nodes.
However, concurrent graph analytics also has some challenges. First, it can be more difficult to implement concurrent graph algorithms than sequential graph algorithms. Second, concurrent graph algorithms can be more prone to race conditions and other concurrency-related issues. Third, concurrent graph analytics can require more memory, as multiple copies of the graph may need to be stored in memory.
Despite these challenges, concurrent graph analytics is a powerful technique that can be used to significantly improve the performance, scalability, and fault tolerance of graph processing applications.
Here are some examples of concurrent graph analytics applications:
- Real-time social network analysis: Concurrent graph analytics can be used to analyze social networks in real time, such as detecting trending topics or identifying suspicious activity.
- Fraud detection: Concurrent graph analytics can be used to detect fraudulent transactions or other types of fraud by identifying patterns in financial networks.
- Recommendation systems: Concurrent graph analytics can be used to power recommendation systems, such as the systems used by e-commerce websites to recommend products to customers.
- Traffic analysis: Concurrent graph analytics can be used to analyze traffic patterns in real time, such as identifying congested roads or predicting travel times.
Concurrent graph analytics is a rapidly evolving field, and new techniques and algorithms are being developed all the time. As graph analytics becomes more and more important in a wide range of applications, we can expect to see concurrent graph analytics play an even greater role in the future.