1
$\begingroup$

I'm trying to identify communities in a direct graph.

I only know how to use Spectral clustering and Girvan-Newman method but the both the methods work only with undirect graph. Am I wrong?

So what method could I use to solve the following problem?

The text of the problem is the following:

Trawling - Identify the communities of the following webgraph with a minimum support of two and a minimum itemset size of two. Plot the resulting bipartite graphs.

enter image description here

What I tried to do was using Spectral Clustering: I transcribed the graph but what I obtained was a squared non-symmetric Adjacency matrix (A).

When there is an arrow from 1 to 2 the value a12 in the matrix is 1 instead the value a21 is 0.

Now I've problems calculating the Degree Matrix (D). All its values are 0 except for the ones along the main diagonal that are the sum of the values in their rows. Is it correct?

Finally I calculate the Laplacian Matrix (L) computing: L=D-A

Now I'm stuck I don't know how to go on, how do I calculate Eigenvalues and Eigenvectors?

$\endgroup$
  • 1
    $\begingroup$ Can you explain what are the support and itemset size? The question that you are asking is clearly community detection in directed graphs, for which there are some algorithms, but the problem that you are trying to solve Trawling is not clearly defined. $\endgroup$ – orezvani Sep 4 '16 at 7:56
  • $\begingroup$ Don't use the sophisticated algorithms. Instead, use the definitions in the question to find out (using brute force) the communities per the definition in the question. $\endgroup$ – Yuval Filmus Sep 25 '16 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.