Graph Communities

By for December 1, 2016

154 views
57 downloads

Language

Report Abuse
Graph Communities is used to find communities in a network graph or to perform graph clustering.
This is a part of a series of custom modules based on the CRAN [igraph][1] package. Graph Communities is used to find communities in a network graph or to perform graph clustering. The left input port is the graph dataset and needs to be represented in two columns as a list of edges where each value in each column represents a Node Id and each row represents an Edge, as shown here. The column names are not relevant. ![img1][i1] The right input port is optional and represents edge weights. When used, those edge weights are considered for the selected community finding algorithm (when applicable for the algorithm). In this case, input data needs to be a single column dataset as shown here. The column name is not relevant. ![img2][i2] Here is an example showing how to use this custom component. ![img3][i3] In this example above, network_1000.csv was generated using available code as described in “Lancichinetti, Andrea, Santo Fortunato, and Filippo Radicchi: Benchmark graphs for testing community detection algorithms. Physical Review E 78.4 (2008): 046110”. The algorithm used for finding communities is the Louvain Algorithm. For more information about the algorithms available in this module, please see the references below. - [Louvain Algorithm][2] - [Infomap Algorithm][3] - [Walktrap Algorithm][4] - [Fast Greedy Algorithm][5] - [Label Propagation Algorithm][6] - [Spinglass Algorithm][7] In addition to the algorithms listed above, which are implemented in igraph, the Spectral Clustering algorithm is also available. This is an implementation from the [kernlab package][8] (please see the specc method). All but the Spinglass and Spectral Clustering algorithms don’t require a specified number of communities as an input parameter. They will try to find an optimal number of communities. If Spinglass or Spectral Clustering are used and the Number of Communities parameter is not specified, it is assumed to be N / sqrt(N), where N is the number of nodes in the graph. This is what the output of the module looks like for this graph. Here the algorithm used was the Louvain Algorithm. ![img4][i4] [1]:http://igraph.org/r/ [2]:http://igraph.org/r/doc/cluster_louvain.html [3]:http://igraph.org/r/doc/cluster_infomap.html [4]:http://igraph.org/r/doc/cluster_walktrap.html [5]:http://igraph.org/r/doc/cluster_fast_greedy.html [6]:http://igraph.org/r/doc/cluster_label_prop.html [7]:http://igraph.org/r/doc/cluster_spinglass.html [8]:https://cran.r-project.org/web/packages/kernlab/kernlab.pdf [i1]:https://alvilcek.blob.core.windows.net/azuremlcustommodules/Azure%20ML%20Custom%20Modules/documentation/Graph_Communities_1.PNG [i2]:https://alvilcek.blob.core.windows.net/azuremlcustommodules/Azure%20ML%20Custom%20Modules/documentation/Graph_Communities_2.PNG [i3]:https://alvilcek.blob.core.windows.net/azuremlcustommodules/Azure%20ML%20Custom%20Modules/documentation/Graph_Communities_3.PNG [i4]:https://alvilcek.blob.core.windows.net/azuremlcustommodules/Azure%20ML%20Custom%20Modules/documentation/Graph_Communities_4.PNG