1
$\begingroup$

I am working on graphs/networks where nodes and edges have some attributes.

I want to know what algorithm exist for:

1) clustering a graph to k groups: depend only on the structure (edge attribute only)

2) Community Detection: ( same as graph clustering) but the number of communities is unknown.

3) Classification: a supervised method where I have labels and I want to classify the nodes based on their attributes and their connections (edges).

4) Page Rank: detecting the most important nodes in a group (community, cluster) based on their connection

thank you very much.

Improve this question
$\endgroup$
0
$\begingroup$

Well ... Some points. Networked data is modeled with graphs. When you have different attributes you have Property Graph.

For clustering, you can extract the topology of the subgraph based on desired attributes and then use any Modularity-based algorithm (most recommended is Blondel algorithm). In Blondel algorithm you don't need to know the number of communities in advance.

Have a look at Network Science book by Barabasi to get more insight to networks.

For classification you may extract features from graphs and use common classification algorithms or use graph kernels and feed it to kernel methods such as SVM. Follow this.

Page rank is one of the methods for ranking but you have simpler choices according to your problem. See Centrality measures from the book above. There you can also see details of different ranking algorithms.

If you need more info you may drop a comment here.

Hope it helped. Good Luck!

Improve this answer
$\endgroup$
11
  • $\begingroup$ Hello, I have been reading state of the art method regarding the problems I have and I have some questions to ask: $\endgroup$ – Mohamed Amine Ouali Jul 6 '18 at 20:27
  • $\begingroup$ 1-for the clustering problem I have seen methods based on minimum cuts like Gomory–Hu tree but when reading some survey it doesn't figure out with the other algorithm such as spectral clustering arxiv.org/pdf/0908.1062v2.pdf I want to know why? $\endgroup$ – Mohamed Amine Ouali Jul 6 '18 at 20:27
  • $\begingroup$ 2 you said that in the clustering I need to extract some the topology of the subgraph based on attributes but in my case I only want to take the current connection in the graph as if the node don’t have attribute (for the clustering I only need to take the arcs attributes “weights” into consideration) $\endgroup$ – Mohamed Amine Ouali Jul 6 '18 at 20:27
  • $\begingroup$ 3 for the classification problem I want to know how to represent the connection (arc) between the nodes as attributes. I read something about GCN (graph convolutional neural network) which take the different connection of a node into consideration. SO I want to know what are the traditional methods for taking the connection into consideration if I will not use GCN $\endgroup$ – Mohamed Amine Ouali Jul 6 '18 at 20:28
  • $\begingroup$ 1) The paper you mentioned is a standard survey for Community detection. Both Andrea and Santo Fortunato are experts in this field. The reason comes from a funny fact :D This problem has been studied in 3 different fields for a long time with some overlap but not completely! In Statistical Physics (where these guys come from) you call it "Community Detection", in CS they call it "Graph Clustering" (see Ulrike Von Luxburg) and in Mathematics they call it "Graph Partitioning" (see Miroslav Fiedler). So you have 3 approaches to the same problem which do not necessarily overlap whole the time! $\endgroup$ – Kasra Manshaei Jul 16 '18 at 10:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.