2
$\begingroup$

Given a weighted, oriented, connected graph with $10^7$ vertices and $10^{10}$ edges I need to implement the algorithm for searching various patterns on this graph for less than polynomial time.

Graph node degree can vary from $1$ to $2*10^5$, nodes and edges also have categorical attributes, that can be indexed and used during the pattern search.

Patterns are subgraphs with 5-100 nodes, some examples are shown on the pictures below, multiple edges from one node and looping is possible. The algorithm can be greedy and find only part of all pattern matchings.

pattern example 1

pattern example 2

I'm looking for a greedy library or method that performs multiple parallel walks on the graph to find the required pattern. It looks like "hub" nodes with a high degree make DFS ineffective for this problem.

$\endgroup$
1
  • 1
    $\begingroup$ Finding cycles in graphs is hard. Most motif-finding approaches focus on considerably smaller examples than the ones you show here, e.g., 3 or 4 vertices. Take a look here: en.wikipedia.org/wiki/Network_motif $\endgroup$ Feb 21, 2019 at 16:05

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.