Apply Clauset-Newman-Moore algorithm to Clusters in a group

Mar 18, 2014 at 7:51 AM
Hi,

I am trying to implement Clauset-Newman-Moore algorithm for my graph( node XL and .net)..
I have created 2 groups and added different vertices into it...
I could group it together... Expand as well collapse..
My requirement is to apply Clauset-Newman-Moore algorithm to Clusters the graph.. I am not able to do..

Can anybody show one example in dot.net

here is my clode snippet

GroupInfo Group1 = new GroupInfo();
            Group1.Name = "Group1";
            GroupInfo Group2 = new GroupInfo();
            Group2.Name = "Group2";
if (vertexMetaKeys.Contains("vertex.color"))
            {
                foreach (IVertex vertex in nodeXLControl1.Graph.Vertices)
                {
                    vertex.SetValue(ReservedMetadataKeys.PerColor, System.Drawing.Color.FromName((string)vertex.GetValue("vertex.color")));
                    vertex.SetValue(ReservedMetadataKeys.PerVertexToolTip, vertex.GetValue("name"));
                    if (vertex.GetValue("vertex.color").ToString() == "red")
                    {
                        vertex.SetValue(ReservedMetadataKeys.PerVertexShape, VertexShape.Sphere);
                        vertex.SetValue(ReservedMetadataKeys.PerColor, System.Drawing.Color.FromName("red"));
                        Group1.Vertices.AddFirst(vertex);
                        vertex.Tag = "Group1";

                    }
                    else
                    {
                        Group2.Vertices.AddFirst(vertex);
                       vertex.Tag = "Group2";
                                                }

                }
            }
nodeXLControl1.Graph.SetValue(ReservedMetadataKeys.GroupInfo, new GroupInfo[] { Group1, Group2 });
Mar 19, 2014 at 1:39 AM
I'll include a complete sample program in my next post. Please note:
  1. The program assumes that there is a NodeXLControl named "nodeXLControl" in your WPF window.
  2. The program works only with NodeXL Class Libraries 1.0.1.320 or later.
  3. The program must target .NET Framework 4.0 or later. (I used .NET Framework 4.5.)
  4. In your Visual Studio solution, you must include references to Smrf.NodeXL.Algorithms.dll, Smrf.NodeXL.Control.Wpf.dll, Smrf.NodeXL.Core.dll, Smrf.NodeXL.Layouts.dll, and Smrf.NodeXL.Visualization.Wpf.
  5. In your Visual Studio solution, you must add SnapGraphMetricCalculator.exe as an item with a "Build Action" of "Content" and a "Copy to Output Directory" value of "Copy if newer". This causes SnapGraphMetricCalculator.exe to be placed in your bin\Debug folder when you build the solution. This executable MUST be in that folder.
-- Tony
Mar 19, 2014 at 1:40 AM
using System;
using System.Windows;
using System.Collections.Generic;
using Smrf.NodeXL.Core;
using Smrf.NodeXL.Algorithms;
using Smrf.NodeXL.Layouts;

namespace NodeXLGroupsSampleCode
{
public partial class MainWindow : Window
{
public MainWindow()
{
    InitializeComponent();

    CreateAndShowGroups();
}

private void
CreateAndShowGroups()
{
    // Create a new graph.

    IGraph graph = new Graph(GraphDirectedness.Directed);
    IVertexCollection vertices = graph.Vertices;
    IEdgeCollection edges = graph.Edges;

    // Add some sample vertices and connect them with edges.

    IVertex vertexA = vertices.Add();
    IVertex vertexB = vertices.Add();
    IVertex vertexC = vertices.Add();
    IVertex vertexD = vertices.Add();
    IVertex vertexE = vertices.Add();
    IVertex vertexF = vertices.Add();

    edges.Add(vertexA, vertexB, true);
    edges.Add(vertexA, vertexC, true);
    edges.Add(vertexD, vertexE, true);
    edges.Add(vertexD, vertexF, true);

    // Use a ClusterCalculator to partition the graph's vertices into
    // clusters.

    ClusterCalculator clusterCalculator = new ClusterCalculator();

    ICollection<Community> clusters =
        clusterCalculator.CalculateGraphMetrics(graph);

    // One group will be created for each cluster.

    List<GroupInfo> groups = new List<GroupInfo>();

    foreach (Community cluster in clusters)
    {
        // Create a group.

        GroupInfo group = new GroupInfo();
        groups.Add(group);

        // Populate the group with the cluster's vertices.

        foreach (IVertex vertex in cluster.Vertices)
        {
            group.Vertices.AddLast(vertex);
        }
    }

    // Store the group information as metadata on the graph.

    graph.SetValue(ReservedMetadataKeys.GroupInfo, groups.ToArray());

    // Assign the graph to the NodeXLControl.

    nodeXLControl.Graph = graph;

    // Tell the layout class to use the groups.

    nodeXLControl.Layout.LayoutStyle = LayoutStyle.UseGroups;

    // Tell the layout class how to lay out the groups.

    nodeXLControl.Layout.BoxLayoutAlgorithm =
        BoxLayoutAlgorithm.ForceDirected;

    // Tell the NodeXLControl to lay out and draw the graph.

    nodeXLControl.DrawGraph(true);
}
}

}
Mar 21, 2014 at 1:34 PM
Hi thanks,

I just wanted to show the graph like this.. How to modify for color combination

http://nodexlgraphgallery.org/Pages/Graph.aspx?graphID=17692
Mar 21, 2014 at 2:47 PM
And what basis the clustering groups has been created..

e.g

ICollection<Community> clusters =
    clusterCalculator.CalculateGraphMetrics(graph);
this line creates 46 clusters in my case.. what is the criteria for creating the groups
Mar 21, 2014 at 4:20 PM
You have to set the color and shape of each vertex in each group. The colors and shapes are up to you.

You set a vertex color like this:
vertex.SetValue(ReservedMetadataKeys.PerColor, System.Drawing.Color.LemonChiffon)
And you set a vertex shape like this:
vertex.SetValue(ReservedMetadataKeys.PerVertexShape, Smrf.NodeXL.Visualization.Wpf.VertexShape.Square)
-- Tony
Mar 21, 2014 at 4:31 PM
On your criteria question, the ClusterCalculator class uses a clustering algorithm called Clauset Newman Moore that attempts to identify groups that have a high density of edges within the groups and a low density of edges between the groups. The algorithm is described here by the original authors:

http://www.ece.unm.edu/ifis/papers/community-moore.pdf

-- Tony
Mar 28, 2014 at 11:44 AM
Thanks Tony, I am able to apply moore algorithm.

One thing I noticed that when I have 5000 or more no. of nodes on the graph and apply the moore's algorithm, the clustered graph taken lot of time ( 900 seconds or more to load)...

Why is this take so much time ..fyi - I have around 900 clusters in this scenarios.. but it works as expected when the node count is 1000-2000..
Does this cluster impact the time taken??

Thanks,

Suryansu
Mar 29, 2014 at 6:31 PM
Hello, Suryansu:

There are several algorithms in NodeXL that slow down dramatically as vertex and edge counts increase, so the behavior you are describing does not surprise me.

Here is the "big O" notation for the Clauset-Newman-Moore algorithm, quoted directly from the original authors:

"Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O(m d log n) where d is the depth of the dendrogram describing the community structure."

-- Tony
Oct 16, 2014 at 7:20 PM
Hi Tony,

Can you explain your 5th point again? I'm not able to add SnapGraphicCalculator.exe
Thanks.
Oct 16, 2014 at 7:22 PM
tcap479 wrote:
I'll include a complete sample program in my next post. Please note:
  1. The program assumes that there is a NodeXLControl named "nodeXLControl" in your WPF window.
  2. The program works only with NodeXL Class Libraries 1.0.1.320 or later.
  3. The program must target .NET Framework 4.0 or later. (I used .NET Framework 4.5.)
  4. In your Visual Studio solution, you must include references to Smrf.NodeXL.Algorithms.dll, Smrf.NodeXL.Control.Wpf.dll, Smrf.NodeXL.Core.dll, Smrf.NodeXL.Layouts.dll, and Smrf.NodeXL.Visualization.Wpf.
  5. In your Visual Studio solution, you must add SnapGraphMetricCalculator.exe as an item with a "Build Action" of "Content" and a "Copy to Output Directory" value of "Copy if newer". This causes SnapGraphMetricCalculator.exe to be placed in your bin\Debug folder when you build the solution. This executable MUST be in that folder.
-- Tony
Hi Tony,

Can you explain your 5th point again? Im not able to find the option to add SnapGraphMetricCalculator.exe as an item.
Thanks.
Oct 17, 2014 at 3:51 PM
  1. In Solution Explorer, right-click your project and select Add, Existing Item from the right-click menu.
  2. In the Add Existing Item dialog box, browse to and select SnapGraphMetricCalculator.exe. You will have to change the filter in the lower-right corner of the dialog box to "All Files" to be able to browse to executable files like SnapGraphMetricCalculator.exe.
  3. Click the Add button.
  4. Select SnapGraphMetricCalculator.exe in Solution Explorer.
  5. In the Properties window, set "Build Action" to "Content" and "Copy to Output Directory" to "Copy if newer."
Oct 19, 2014 at 9:05 AM
Hi Tony,
Thanks for the help. I'm trying to execute the Calculate Graph Metrics programmatically and i cannot find the proper function. I have a console application(using C#) that opens the NodeXL document. But i cannot find the function to execute Calculate Graph Metrics on that workbook. What is the name of the function that calculates the graph metrics programmatically and how do i call it?
Oct 19, 2014 at 7:06 PM
I don't understand your scenario. You're opening a NodeXL workbook from your console application and you want to calculate graph metrics on the workbook? There is no method for that. The only way to calculate graph metrics on a workbook is through the UI of the NodeXL Excel Template.

Or did you mean that you have your own Smrf.NodeXL.Core.Graph object and you want to calculate graph metrics for the Graph? In that case, you can use the family of classes implemented in the Smrf.NodeXL.Algorithms namespace, like VertexDegreeCalculator and OverallMetricCalculator, which take a Graph object and return metrics for the graph. Those are documented in the NodeXLApi.chm help file. Search for the "Smrf.NodeXL.Algorithms Namespace" topic.

You can find a few code sample here:

http://nodexl.codeplex.com/discussions/285157