Finding all k-size subgraphs

I have no experience with advanced combinatorics, but I have to solve a problem that I think I will need advanced combinatorial techniques, correct me if I am wrong.

Let $G$ be a large directioned graph with its vertices numerically labeled, I need to find all subgraphs of size $k$ (by size I mean number of vertices) in $G$. (By large I mean values up to 1 billion vertices).

My first though was to iterate over all vertices of $G$ making them root for $k$-sized subgraphs, after getting the root vertex $u$ I would build implicit trees where a child vertex is connect to its parent either with an incoming or outgoing edge. A basic restriction would be that a vertex can be listed in the tree only once, for that I could keep a visited-vertices list. In order to avoid repetition I could add a constraint that the label of a child can never be higher than i̶t̶s̶ ̶p̶a̶r̶e̶n̶t̶'s̶ ̶l̶a̶b̶e̶l̶ the root's label.

Up to this point I think my approach is fine, but now I have to generate all possible trees, because I can be selecting $k$ vertices in a $k$-depth tree, one at each level, or have a $l$-depth ($1<l<k$) tree and be selecting more than one vertice in one level.

For doing that I think maybe integer composition methods can help, by integer composition I mean all possible ways to create an integer number from the sum of at least 2 other integer numbers different from zero where the order of adding matters. I have searched about that and I came across texts that said that using a revolving door ordering algorithm is the fastest way to generate all possible combinations.

The problem is that information I have found about revolving door ordering algorithms are somewhat heavy on combinatorics, a field I don't have deeply studied yet.

If it matters somehow, I am a Computer Science bachelor student, so I think that a more algorithmic approach on the revolving door ordering can help me, don't get me wrong, I can handle the mathematics, but by now, I am not able to visualize the strong mathematical approaches as clear algorithms.

• Do the subgraphs have to be induced subgraphs meaning if they contain the vertices $v_1,v_2,\ldots,v_m$ then they also contain all the edges between the vertices? Or do the vertices just have to be connected somehow in the graph? For example, if we look at the complete graph on three vertices (a triangle), are we saying there is only one subgraph of three vertices (the triangle), or are there four subgraphs? – user2154420 May 13 '15 at 2:39
• @user2154420 yes, they are induced subgraphs. Whenever there is an edge $E$, in $G$, between the vertices of a subgraph $G′$, $E$ is in $G′$ too. In your example, there would be only one subgraph of three vertices. – Rodrigo Martins May 13 '15 at 3:12

Judging from your description, you're seeking (weakly) connected subgraphs. In this case, the fastest algorithm I've encountered for complete enumeration is the ESU algorithm (ref.), which was developed by Sebastian Wernicke for his network motif detection package called Fanmod. It visits each $k$-node subgraph exactly once.

If you're talking about graphs with billions of nodes (and consequently zillions of $k$-node subgraphs), full enumeration is unlikely to run in a reasonable amount of time, and you'll likely be stuck finding an estimation of the number of subgraphs.

• Thanks, I'll try that today. By the way my problem is related to motif detection, currently I am trying to reproduce the results obtained by Kavosh algorithm, which is faster than Fanmod in most cases and doesn't have a limit for k. After I will try finding some way to work it out for large networks (1 billion nodes). – Rodrigo Martins May 14 '15 at 13:41
• Sorry for the delay, I was trying to implement the solution you proposed, but as it focuses on edge choosing, I would have to modify many parts of my code as it is all made up with vertex choosing in mind. So I spent the last days trying to figure out how to understand the revolving door ordering algorithm and I failed, but I found another way to do this that didn't require many changes in my code. Anyway thanks for your help! – Rodrigo Martins May 20 '15 at 14:09

[This partially answer the question, because this solution doesn't use the revolving door ordering algorithm, which is stated over literature as the best (i.e., computationally efficient) algorithm to the task]

I didn't understand really well the revolving door ordering algorithm so I didn't implement it, of course I could just code the algorithm without understanding, but that's not my objective.

While trying to figure out how the RD ordering works I though another way to implement an algorithm to generate all possible combinations with a relative low computational cost (probably it is not the fastest way, but I don't think it is slow either).

Enumeration algorithm

Description

To enumerate all $k$-sized subgraphs I first mapped all neighbors from each vertex in a 2D vector where each column represents a vertex and the numbers in it represents neighbors from that vertex. I also kept a visited vertices list.

I iterated through each vertex from the network making it root for new subgraphs. After the root is chosen, in order to proceed with an implicit tree building approach, I create a list of valid children for that vertex respecting the rule that a child vertex can never have a greater label than the root vertex's label (in the question I proposed that the label of a child could never be greater than the label of its parent, but that was wrong as certain combinations would be skipped) in order to avoid duplicated subgraphs and then I marked all vertices in that list as visited to prevent a vertex appearing more than once in the tree. A child of a vertex is either connected to the root in $G$ by an incoming edge or outgoing.

Then I create a loop where an integer $i$ goes from 1 to the minimum value between the number of remaining vertices to compose the $k$-subgraph and the length of the valid children list.

Inside the loop I generate all possible combinations of choosing $i$ vertices where I recursively exclude the first vertex from the valid children list until it's length is equal to $i$, than I revolve each recursion removing the second vertex and so on. To avoid duplicated combinations I keep a vector called Index to store which vertex I will exclude at each recursive call as I know the number of recursive calls will be equal to the original list of valid children minus $i$ I know the length of Index. Index starts with all it's values set to zero and then I increase the number in last position by one until it's value overpasses $i$, then I "send one" unit to the position before in Index and repeat it if that position now overpasses $i$ too (like in addition, e.g., 599 + 1 you have 59(10), send one to next number, you get 5(10)0 and send one again and you get 600); then if the current position I "am" in Index is zero and it overpasses $i$ I set it to 0. Then I iterate toward the end of Index "normalizing" the numbers, where the number of a position is set back to the value of the position before (not to 0 to avoid duplicated combinations, this way a vertex once excluded will never be excluded again).

Then I recursively generate more lists of valid children from the combination of vertices chosen at the last call until $k$ vertices are chosen and I store they in a subgraph list or if no sufficient vertices were found to compose the $k$-subgraph I do nothing.

Implementation (in C++)

#include <GraphData.hpp>
#include <stdio.h>
#include <vector>
#include <algorithm>

struct GD::Cell {
std::vector<int> vertices;
Cell* next;
};

GD::GraphList::GraphList() {
ini = new Cell;
cursor = ini;
}

GD::GraphList::~GraphList() {

}

Cell* aux = new Cell;
cursor->next = aux;
cursor = aux;
}

int counter = 0; // counter to count the number of k-subgraphs found
void GD::Enumerate(TNGraph G, int k, GD::GraphList *kSubgraphs) {
std::vector<std::vector<int>> Neighbors(G.GetNodes());
GD::mapNeighbors(G, Neighbors);                                             // map neighbors for all vertices to avoid repeatly discovering the neighborhood of a vertex
for(int i=0; G.IsNode(i); i++) {                                            // iterate through all vertices of G
std::vector<bool> Visited(G.GetNodes());                                // list to keep track of visited vertices
Visited[i] = true;                                                      // mark the current root as visited
std::vector<int> S(1);                                                  // vertices selected in current level
S = i;                                                               // only the root is selected in the first level
std::vector<int> subgraph(S);                                           // vector to store the vertices of the subgraph
GD::Explore(G, Neighbors, i, Visited, S, subgraph, kSubgraphs, k-1);    // Explore all possible combinations that generete different trees
Visited[i] = false;                                                     // unmark current root as visited at the end
}
printf("\nSubgraphs of size %d found: %d\n", k, counter);
}

void GD::Explore(TNGraph G, std::vector<std::vector<int>> &Neighbors, int root, std::vector<bool> &Visited, std::vector<int> &S, std::vector<int> &subgraph, GD::GraphList *kSubgraphs, int Remainder) {
if(Remainder==0) {                              // if there are no more vertices to select the k-subgraph is formed
kSubgraphs->cursor->vertices = subgraph;    // my data structure
counter++;                                  // count one more k-subgraph discovered
return;
}
std::vector<int> ValList;                                           // create a vector to store valid children at this level of the tree
GD::Validate(G, Neighbors, Visited, S, root, ValList);              // fill the vector with the actual children
int n = std::min((int) ValList.size(), Remainder);                  // get the number of vertices to select at this level
for(int i=1; i<=n; i++) {                                           // iterate from selecting a single vertex to selecting n vertices
std::vector<int> Index(ValList.size()-i, 0);                    // create a vector to keep track of which vertices to delete from ValList in order to generate a combination
std::vector<int> C = GD::genComb(i, ValList, n, Index);         // generate the initial combination
do {                                                                                                                                    // repeat
subgraph.insert(subgraph.end(), C.begin(), C.end());                                                                                    // compose subgraph with the current combination
GD::Explore(G, Neighbors, root, Visited, C, subgraph, kSubgraphs, Remainder-i);                                                         // recursive call to advance to next level of the implicit tree
GD::updateIndex(Index, i);                                                                                                              // update Index to generate the next combination
C = GD::genComb(i, ValList, n, Index);                                                                                                  // generate next combination
subgraph.erase(subgraph.end() - C.size(), subgraph.end());                                                                              // clear old combination from the subgraph "constructor"
} while(!Index.empty() && !((Index==0 && std::adjacent_find(Index.begin(), Index.end(), std::not_equal_to<int>()) == Index.end()))); // until all combinations were tried, i.e. when Index has cycled back to begin (0,0,0,...,0), if empty it just exists one combination
}
for(int i=0; i<ValList.size(); i++) Visited.at(ValList[i]) = false; // unmark selected vertices at current level
}

void GD::mapNeighbors(TNGraph G, std::vector<std::vector<int>> &Neighbors) {
for(int i=0; i<G.GetNodes(); i++)
for(int j=0; j<G.GetNodes(); j++)
if((G.GetNI(i)).IsNbrNId(j))
Neighbors[i].push_back(j);
}

void GD::Validate(TNGraph G, std::vector<std::vector<int>>& Neighbors, std::vector<bool> &Visited, std::vector<int> &S, int root, std::vector<int> &ValList) {
for(int i=0; i<S.size(); i++) {                                                                                 // S is the selected children of the last level (or root)
for(int j=root+1; j<G.GetNodes(); j++) {                                                                    // j is the label of possible children, which can't be greater than root
if(!Visited[j] && std::binary_search((Neighbors.at(S[i])).begin(), (Neighbors.at(S[i])).end(), j)) {    // if not visited and it's in the neighborhood of S[i]
Visited[j] = true;                                                                                  // mark as visited
ValList.push_back(j);                                                                               // include as valid children
}
}
}
}

std::vector<int> GD::genComb(int i, std::vector<int> ValList, int n, std::vector<int> &Index, int level) {
if(ValList.size()==i || Index.empty()) return ValList;          // trivial case, combination is the current ValList itself
ValList.erase(ValList.begin() + Index[level]);                  // enshorten ValList (note that it doesn't modify original ValList as it is just a copy of it)
return GD::genComb(i, ValList, n, Index, level+1);              // recursive call
}

void GD::updateIndex(std::vector<int> &Index, int n) {
if(Index.empty()) return;           // nothing to update if Index is empty
int i = Index.size() - 1;           // go to last position of Index
Index[i]++;                         // increase it
for(i; i>0; i--) {                  // ascend Index
if(Index[i]>n) Index[i-1]++;    // if the current position's value overpasses n "send one" to the position before
else break;                     // if not there is no need to keep ascending
}
if(Index[i]>n) Index[i] = 0;        // if Index[i]>n it means i==0 so no way to "send one" as there is no position before, so cycle back to 0
for(++i; i<Index.size(); i++)       // descend Index to "normalize" it
if(Index[i]>Index[i-1])         // if a lower position value is greater than its "parent's" value
Index[i] = Index[i-1];      // make it equal to its "parent"
}


Obs.: In my code I use the SNAP library to handle manipulation with $G$.