From: Yu Huang (yuhuang_at_[hidden])
Date: 2005-09-07 02:15:52
Yu Huang wrote:
>Hi all,
>
>I coded a program recursively cutting graphs based on
>brandes_betweenness_centrality.
>
>But the weird thing is that it succeeds on small graphs(<=8 vertices,
><=15 edges) and large graphs(~3500 vertices, ~138,000edges). But failed
>on medium-size (~37-200 vertices, ~42-350 edges).
>
>
>
>The failed output is like this:
>
>no_of_vertices: 203
>no_of_edges: 368
>connectivity: 0.0179486
>running brandes_betweenness_centrality... *** glibc detected *** double
>free or corruption (out): 0x080942d8 ***
>Aborted
>
>
>Actually, I can't say the it succeeds on large graph. I stopped it after
>~45 brandes_betweenness_centrality() calls(because it took too long,
>over-night). But on medium-size ones, the first
>brandes_betweenness_centrality() is always ok. But failed quickly,
>mostly 2nd loop, some 3rd, even 5th. Only 0x080942d8 changed from run to
>run. Others remain same(Am i stupid to say this? of course it won't change).
>
>Well, i paste my core function here. The main idea is I remove the edge
>with max centrality and form a vector of clusters(graphs) from the
>ancestor graph's components (if after cut, the ancestor has >=2
>components, otherwise keep cutting on the ancestor graph).
>
>
>void ClusterByEBC::cut_by_betweenness_centrality(Graph &graph, const int
>&size_cutoff, const float &conn_cutoff)
>/*
>*09-04-05
>* cut the graph with the edge of maximum betweenness_centrality
>*/
>{
> int no_of_vertices = num_vertices(graph);
> int no_of_edges = num_edges(graph);
> #ifdef DEBUG
> std::cerr<<"no_of_vertices: "<<no_of_vertices<<std::endl;
> std::cerr<<"no_of_edges: "<<no_of_edges<<std::endl;
> #endif
> if (no_of_vertices>=size_cutoff)
> {
> float connectivity =
>2.0*no_of_edges/(no_of_vertices*(no_of_vertices-1));
> #ifdef DEBUG
> std::cerr<<"connectivity: "<<connectivity<<std::endl;
> #endif
> if (connectivity>=conn_cutoff)
> {
> #ifdef DEBUG
> std::cerr<<"good subgraph "<<std::endl;
> #endif
> good_subgraph_vector.push_back(graph);
> }
> else
> {
> vector<double> edge_centrality(no_of_edges);
> EdgeCentralityMap ec_map(edge_centrality.begin(),
>get(edge_index, graph));
> //"make_iterator_property_map(edge_centrality.begin(),
>get(edge_index, subgraph), double())" also works.
> indirect_cmp<EdgeCentralityMap, std::less<centrality_type> >
>cmp(ec_map);
> #ifdef DEBUG
> std::cerr<<"running brandes_betweenness_centrality... ";
> #endif
> brandes_betweenness_centrality(graph,
>edge_centrality_map(ec_map));
> #ifdef DEBUG
> std::cerr<<"done."<<std::endl;
> #endif
> edgeDescriptor e = *max_element(edges(graph).first,
>edges(graph).second, cmp);
> centrality_type max_centrality = get(ec_map, e);
> #ifdef DEBUG
> std::cerr<<"max_centrality is "<<max_centrality<<std::endl;
> #endif
> remove_edge(e, graph);
> #ifdef DEBUG
> std::cerr<<"after removal the subgraph has
>"<<num_edges(graph)<<" edges."<<std::endl;
> #endif
> std::vector<int> component(num_vertices(graph));
> int no_of_components = connected_components(graph,
>&component[0]);
> if (no_of_components==1) //keep cutting
> {
> #ifdef DEBUG
> std::cerr<<"only one component, keep cutting
>"<<std::endl;
> #endif
> cut_by_betweenness_centrality(graph, size_cutoff,
>conn_cutoff);
> }
> else //first get the connected_components into a
>vector_sub_subgraph and cut them separately
> {
> #ifdef DEBUG
> std::cerr<<"get the connected_components into a
>vector_graph and cut them separately "<<std::endl;
> #endif
> std::vector<Graph> vector_graph =
>graph_components(graph, component, no_of_components);
> std::vector<Graph>::iterator g_iterator;
>
>for(g_iterator=vector_graph.begin();g_iterator!=vector_graph.end();++g_iterator)
> {
> cut_by_betweenness_centrality(*g_iterator,
>size_cutoff, conn_cutoff);
> }
> }
> }
> }
> #ifdef DEBUG
> else
> std::cerr<<"Bad graph, too
>small,"<<no_of_vertices<<"vertices"<<std::endl;
> #endif
>
>}
>
>
>This looks like a hard issue. I searched the mailing list and found one
>similar message,
>http://listarchives.boost.org/MailArchives/ublas/2005/08/0657.php (no one replied).
>
>Thanks,
>Yu
>
>
>
I forgot, if any of you guys wants the complete source code and the
graph data, i'll email you directly. The graph data is too large to be
an attachement.