graph_clustering.hh 5.21 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2015 Tiago de Paula Peixoto <tiago@skewed.de>
4
5
6
7
8
9
10
11
12
13
14
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 3
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
15
// you should have received a copy of the GNU General Public License
16
17
18
19
20
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef GRAPH_CLUSTERING_HH
#define GRAPH_CLUSTERING_HH

21
22
#include "config.h"

Tiago Peixoto's avatar
Tiago Peixoto committed
23
#include <unordered_set>
24
25
#include <boost/mpl/if.hpp>

26
#ifdef HAVE_SPARSEHASH
27
#include SPARSEHASH_INCLUDE(dense_hash_set)
28
29
#endif

Tiago Peixoto's avatar
Tiago Peixoto committed
30
#ifndef __clang__
31
32
#include <ext/numeric>
using __gnu_cxx::power;
Tiago Peixoto's avatar
Tiago Peixoto committed
33
34
35
36
37
38
39
#else
template <class Value>
Value power(Value value, int n)
{
    return pow(value, n);
}
#endif
40

41
42
43
44
namespace graph_tool
{
using namespace boost;

45
46
#ifdef HAVE_SPARSEHASH
using google::dense_hash_set;
Tiago Peixoto's avatar
Tiago Peixoto committed
47
48
#else
using std::unordered_set;
49
50
#endif

51
52
// calculates the number of triangles to which v belongs
template <class Graph>
53
pair<int,int>
54
55
get_triangles(typename graph_traits<Graph>::vertex_descriptor v, const Graph &g)
{
56
57
58
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;

#ifdef HAVE_SPARSEHASH
59
    typedef dense_hash_set<vertex_t, std::hash<vertex_t>> set_t;
60
61
62
63
64
65
66
67
68
69
#else
    typedef unordered_set<vertex_t> set_t;
#endif

    set_t neighbour_set;

#ifdef HAVE_SPARSEHASH
     neighbour_set.set_empty_key(numeric_limits<vertex_t>::max());
     neighbour_set.resize(out_degree(v, g));
#endif
70

71
    size_t triangles = 0;
72

73
74
    typename graph_traits<Graph>::adjacency_iterator n, n_end;
    for (tie(n, n_end) = adjacent_vertices(v, g); n != n_end; ++n)
75
    {
76
        if (*n == v) // no self-loops
77
            continue;
78
79
        neighbour_set.insert(*n);
    }
80

81
82
83
84
    for (tie(n, n_end) = adjacent_vertices(v, g); n != n_end; ++n)
    {
        typename graph_traits<Graph>::adjacency_iterator n2, n2_end;
        for (tie(n2, n2_end) = adjacent_vertices(*n, g); n2 != n2_end; ++n2)
85
        {
86
            if (*n2 == *n) // no self-loops
87
                continue;
88
89
            if (neighbour_set.find(*n2) != neighbour_set.end())
                ++triangles;
90
91
        }
    }
92
93

    size_t k = out_degree(v, g);
94
95
96
97
98
99
100
101
    return make_pair(triangles/2,(k*(k-1))/2);
}


// retrieves the global clustering coefficient
struct get_global_clustering
{
    template <class Graph>
102
    void operator()(const Graph& g, double& c, double& c_err) const
103
104
105
106
107
108
109
    {
        size_t triangles = 0, n = 0;
        pair<size_t, size_t> temp;

        int i, N = num_vertices(g);

        #pragma omp parallel for default(shared) private(i,temp) \
110
            schedule(runtime) if (N > 100) reduction(+:triangles, n)
111
112
113
114
115
116
117
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;

            temp = get_triangles(v, g);
118
            triangles += temp.first;
119
120
            n += temp.second;
        }
121
        c = double(triangles) / n;
122
123
124

        // "jackknife" variance
        c_err = 0.0;
125
        double cerr = 0.0;
126

127
        #pragma omp parallel for default(shared) private(i,temp) \
128
            schedule(runtime) if (N > 100) reduction(+:cerr)
129
130
131
132
133
134
135
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;

            temp = get_triangles(v, g);
136
            double cl = double(triangles - temp.first) / (n - temp.second);
137

138
            cerr += power(c - cl, 2);
139
        }
140
        c_err = sqrt(cerr);
141
142
143
144
145
146
147
    }
};

// sets the local clustering coefficient to a property
struct set_clustering_to_property
{
    template <class Graph, class ClustMap>
148
    void operator()(const Graph& g, ClustMap clust_map) const
149
    {
150
        typedef typename property_traits<ClustMap>::value_type c_type;
151
152
        typename get_undirected_graph<Graph>::type ug(g);
        int i, N = num_vertices(g);
153

154
        #pragma omp parallel for default(shared) private(i) schedule(runtime) if (N > 100)
155
156
157
158
159
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
160

161
162
163
164
            pair<size_t,size_t> triangles = get_triangles(v,ug); // get from ug
            double clustering = (triangles.second > 0) ?
                double(triangles.first)/triangles.second :
                0.0;
165

166
            clust_map[v] = c_type(clustering);
167
168
        }
    }
169

170
171
172
173
    template <class Graph>
    struct get_undirected_graph
    {
        typedef typename mpl::if_
Tiago Peixoto's avatar
Tiago Peixoto committed
174
175
176
177
           <std::is_convertible<typename graph_traits<Graph>::directed_category,
                                directed_tag>,
            const UndirectedAdaptor<Graph>,
            const Graph& >::type type;
178
179
180
    };
};

181
} //graph-tool namespace
182
183

#endif // GRAPH_CLUSTERING_HH