graph_clustering.hh 4.68 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-2016 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"

23
#include "hash_map_wrap.hh"
24
25
#include <boost/mpl/if.hpp>

26
27
28
29
#ifdef USING_OPENMP
#include "omp.h"
#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
45
namespace graph_tool
{
using namespace boost;

// calculates the number of triangles to which v belongs
46
template <class Graph, class VProp>
47
pair<int,int>
48
49
get_triangles(typename graph_traits<Graph>::vertex_descriptor v, VProp& mark,
              const Graph &g)
50
{
51
    size_t triangles = 0;
52

53
    for (auto n : adjacent_vertices_range(v, g))
54
    {
55
        if (n == v)
56
            continue;
57
        mark[n] = true;
58
    }
59

60
    for (auto n : adjacent_vertices_range(v, g))
61
    {
62
63
64
        if (n == v)
            continue;
        for (auto n2 : adjacent_vertices_range(n, g))
65
        {
66
            if (n2 == n)
67
                continue;
68
            if (mark[n2])
69
                ++triangles;
70
71
        }
    }
72

73
74
75
    for (auto n : adjacent_vertices_range(v, g))
        mark[n] = false;

76
    size_t k = out_degree(v, g);
77
    return make_pair(triangles / 2, (k * (k - 1)) / 2);
78
79
80
81
82
83
84
}


// retrieves the global clustering coefficient
struct get_global_clustering
{
    template <class Graph>
85
    void operator()(const Graph& g, double& c, double& c_err) const
86
87
88
89
    {
        size_t triangles = 0, n = 0;
        pair<size_t, size_t> temp;

90
        vector<bool> mask(num_vertices(g), false);
91

92
        int i, N = num_vertices(g);
93
        #pragma omp parallel for default(shared) private(i,temp) \
94
95
            firstprivate(mask) schedule(runtime) if (N > OPENMP_MIN_THRESH) \
            reduction(+:triangles, n)
96
97
        for (i = 0; i < N; ++i)
        {
98
99
            auto v = vertex(i, g);
            if (!is_valid_vertex(v, g))
100
                continue;
101
            temp = get_triangles(v, mask, g);
102
            triangles += temp.first;
103
104
            n += temp.second;
        }
105
        c = double(triangles) / n;
106
107
108

        // "jackknife" variance
        c_err = 0.0;
109
        double cerr = 0.0;
110

111
        #pragma omp parallel for default(shared) private(i,temp) \
112
113
            firstprivate(mask) schedule(runtime) if (N > OPENMP_MIN_THRESH) \
            reduction(+:cerr)
114
115
        for (i = 0; i < N; ++i)
        {
116
117
            auto v = vertex(i, g);
            if (!is_valid_vertex(v, g))
118
                continue;
119
            temp = get_triangles(v, mask, g);
120
            double cl = double(triangles - temp.first) / (n - temp.second);
121

122
            cerr += power(c - cl, 2);
123
        }
124
        c_err = sqrt(cerr);
125
126
127
128
129
130
131
    }
};

// sets the local clustering coefficient to a property
struct set_clustering_to_property
{
    template <class Graph, class ClustMap>
132
    void operator()(const Graph& g, ClustMap clust_map) const
133
    {
134
        typedef typename property_traits<ClustMap>::value_type c_type;
135
136
        typename get_undirected_graph<Graph>::type ug(g);
        int i, N = num_vertices(g);
137

138
        vector<bool> mask(num_vertices(g), false);
139
140

        #pragma omp parallel for default(shared) private(i) \
141
            firstprivate(mask) schedule(runtime) if (N > OPENMP_MIN_THRESH)
142
143
        for (i = 0; i < N; ++i)
        {
144
145
            auto v = vertex(i, g);
            if (!is_valid_vertex(v, g))
146
                continue;
147
            auto triangles = get_triangles(v, mask, ug); // get from ug
148
149
150
            double clustering = (triangles.second > 0) ?
                double(triangles.first)/triangles.second :
                0.0;
151
            clust_map[v] = c_type(clustering);
152
153
        }
    }
154

155
156
157
158
    template <class Graph>
    struct get_undirected_graph
    {
        typedef typename mpl::if_
Tiago Peixoto's avatar
Tiago Peixoto committed
159
160
161
162
           <std::is_convertible<typename graph_traits<Graph>::directed_category,
                                directed_tag>,
            const UndirectedAdaptor<Graph>,
            const Graph& >::type type;
163
164
165
    };
};

166
} //graph-tool namespace
167
168

#endif // GRAPH_CLUSTERING_HH