Changeset 0075ec

Timestamp:

07/02/07 20:33:37 (6 years ago)

Author:

Tiago de Paula Peixoto <tiago@…>

Branches:

master, python3

Children:

393242

Parents:

ba2aee

git-author:

Tiago de Paula Peixoto <tiago@…> (07/02/07 20:33:37)

git-committer:

Tiago de Paula Peixoto <tiago@…> (07/02/07 20:33:37)

Message:

* normalize betweenness centrality
* include central point dominance


git-svn-id: https://svn.forked.de/graph-tool/trunk@103 d4600afd-f417-0410-95de-beed9576f240

Location:

src

Files:

• graph-tool (modified) (4 diffs)
• graph/graph.hh (modified) (1 diff)
• graph/graph_betweenness.cc (modified) (4 diffs)
• graph/graph_bind.cc (modified) (1 diff)

src/graph-tool

@@ -114 +114 @@
 statistics.add_option("--minimum-spanning-tree", action="callback", callback=push_option, type="string", metavar="[WEIGHT|]PROPERTY", help="mark the minimum spanning tree edges in PROPERTY")
 statistics.add_option("--line-graph", action="callback", callback=push_option, type="string", metavar="FILE[|FORMAT]", help="save the corresponding line graph to FILE")
-statistics.add_option("--betweenness-centrality", action="callback", callback=push_option, type="string", metavar="VERTEX_BETWEENESS[EDGE_BETWEENESS]", help="calculate and store the vertex and/or edge betweenness centrality")
+statistics.add_option("--betweenness-centrality", action="callback", callback=push_option, type="string", metavar="VERTEX_BETWEENESS[|EDGE_BETWEENESS[|WEIGHT]]", help="calculate and store the vertex and/or edge betweenness centrality")
+statistics.add_option("--central-point-dominance", action="callback", callback=push_option, type="string", metavar="VERTEX_BETWEENESS|FILE", help="calculate central point dominance, given the VERTEX_BETWEENESS vertex property")
+
 
 correlations =  parser.add_option_group("Correlations")
@@ -125 +127 @@
 
 clustering =  parser.add_option_group("Clustering")
-clustering.add_option("--set-local-clustering-to-property", action="callback", callback=push_option, type="string", metavar="PROPERTY", help="set the local clustering coefficient to vertex property")
+clustering.add_option("--local-clustering-coefficient", action="callback", callback=push_option, type="string", metavar="PROPERTY", help="set the local clustering coefficient to vertex property")
 clustering.add_option("--global-clustering-coefficient", action="callback", callback=push_option, type="string", metavar="FILE", help="get the global clustering coefficient")
-clustering.add_option("--set-extended-clustering-to-property", action="callback", callback=push_option, type="string", metavar="PREFIX|MAX", help="set the extended clustering coefficients c1 to cMAX to vertex properties PREFIX1 to PREFIXMAX")
+clustering.add_option("--extended-clustering-coefficient", action="callback", callback=push_option, type="string", metavar="PREFIX|MAX", help="set the extended clustering coefficients c1 to cMAX to vertex properties PREFIX1 to PREFIXMAX")
 
 layout =  parser.add_option_group("Layout")
@@ -523 +525 @@
             weight = ""
         graph.GetBetweenness(weight, vertex_centrality, edge_centrality)
+    elif opt.name == "central-point-dominance":
+        values = parse_values(opt.value)
+        if len(values) != 2:
+            raise OptionError(opt.name, "invalid value '%s'" % opt.value)
+        if just_file:
+            return None
+        return (graph.GetCentralPointDominance(values[0]), values[1])
     elif opt.name == "vertex-correlation-histogram":
         values = parse_values(opt.value)
@@ -601 +610 @@
         ret = "%f\t%f" % (avg, dev)
         return (ret, opt.value)
-    elif opt.name == "set-local-clustering-to-property":
+    elif opt.name == "local-clustering-coefficient":
         if just_file:
             return None
         graph.SetLocalClusteringToProperty(opt.value)
-    elif opt.name == "set-extended-clustering-to-property":
+    elif opt.name == "extended-clustering-coefficient":
         if just_file:
             return None

src/graph/graph.hh

@@ -99 +99 @@
     void   GetLineGraph(std::string out_file, std::string format);
     void   GetBetweenness(std::string weight, std::string edge_betweenness, std::string vertex_betweenness);
-
+    double GetCentralPointDominance(std::string vertex_betweenness);
+    
     // community structure
     enum comm_corr_t

src/graph/graph_betweenness.cc

@@ -36 +36 @@
 using namespace graph_tool;
 
+template <class Graph, class VertexBetweenness, class EdgeBetweenness>
+void normalize_betweenness(const Graph& g, VertexBetweenness vertex_betweenness, EdgeBetweenness edge_betweenness)
+{
+    size_t n = HardNumVertices()(g);
+    double factor = 2.0/(n*n - 3*n + 2);
+
+    typename graph_traits<Graph>::vertex_iterator v, v_end;
+    for (tie(v, v_end) = vertices(g); v != v_end; ++v) 
+    {
+        put(vertex_betweenness, *v, factor * get(vertex_betweenness, *v));
+    }
+
+    typename graph_traits<Graph>::edge_iterator e, e_end;
+    for (tie(e, e_end) = edges(g); e != e_end; ++e) 
+    {
+        put(edge_betweenness, *e, factor * get(edge_betweenness, *e));
+    }
+}
+
 struct get_betweenness
 {    
@@ -42 +61 @@
     {        
         brandes_betweenness_centrality(g, vertex_index_map(index_map).edge_centrality_map(edge_betweenness).centrality_map(vertex_betweenness));
+        normalize_betweenness(g, vertex_betweenness, edge_betweenness);
     }
 };
@@ -61 +81 @@
             weight_map = get_static_property_map<weight_map_t>(find_property_map(_dp, _weight, typeid(graph_traits<typename GraphInterface::multigraph_t>::edge_descriptor)));
             brandes_betweenness_centrality(_g, vertex_index_map(_vertex_index).weight_map(weight_map).edge_centrality_map(_edge_betweenness).centrality_map(_vertex_betweenness));
+            normalize_betweenness(_g, _vertex_betweenness, _edge_betweenness);
             _found = true;
         }
@@ -165 +186 @@
 
 }
+
+struct get_central_point_dominance
+{    
+    template <class Graph, class VertexBetweenness>
+    void operator()(Graph& g, VertexBetweenness vertex_betweenness, double& c) const
+    {        
+        c = central_point_dominance(g, vertex_betweenness);
+    }
+};
+
+
+double GraphInterface::GetCentralPointDominance(string vertex_betweenness)
+{
+    try
+    {
+        typedef DynamicPropertyMapWrap<double, graph_traits<multigraph_t>::vertex_descriptor> betweenness_map_t;
+        betweenness_map_t betweenness(find_property_map(_properties, vertex_betweenness, typeid(graph_traits<multigraph_t>::vertex_descriptor)));
+        double c = 0.0;
+        
+        bool reversed = this->GetReversed();
+        bool directed = this->GetDirected();
+        check_filter(*this, bind<void>(get_central_point_dominance(), _1, var(betweenness), var(c)), never_reversed(), always_directed());
+        this->SetReversed(reversed);
+        this->SetDirected(directed);
+        return c;
+    }
+    catch (property_not_found) 
+    {
+        throw GraphException("vertex property " + vertex_betweenness + " not found");
+    }
+}

src/graph/graph_bind.cc

@@ -241 +241 @@
         .def("GetLineGraph", &GraphInterfaceWrap::GetLineGraph)
         .def("GetBetweenness", &GraphInterfaceWrap::GetBetweenness)
+        .def("GetCentralPointDominance", &GraphInterfaceWrap::GetCentralPointDominance)
         .def("GetCommunityStructure", &GraphInterfaceWrap::GetCommunityStructure)
         .def("GetCommunityNetwork", &GraphInterfaceWrap::GetCommunityNetwork)