graph_clustering.hh 4.92 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-2020 Tiago de Paula Peixoto <tiago@skewed.de>
4
5
//
// This program is free software; you can redistribute it and/or
6
// modify it under the terms of the GNU Lesser General Public License
7
8
9
10
11
12
// 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
13
// GNU Lesser General Public License for more details.
14
//
15
// you should have received a copy of the GNU Lesser 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
#ifdef _OPENMP
27
28
29
#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
namespace graph_tool
{
using namespace boost;
44
using namespace std;
45
46

// calculates the number of triangles to which v belongs
47
48
49
template <class Graph, class EWeight, class VProp>
auto get_triangles(typename graph_traits<Graph>::vertex_descriptor v,
                   EWeight& eweight, VProp& mark, const Graph& g)
50
{
51
    typedef typename property_traits<EWeight>::value_type val_t;
52
    val_t triangles = 0, k = 0;
53

54
    for (auto e : out_edges_range(v, g))
55
    {
56
        auto n = target(e, g);
57
        if (n == v)
58
            continue;
59
60
61
        auto w = eweight[e];
        mark[n] = w;
        k += w;
62
    }
63

64
    for (auto e : out_edges_range(v, g))
65
    {
66
        auto n = target(e, g);
67
68
        if (n == v)
            continue;
69
70
71
        auto m = mark[n];
        mark[n] = 0;
        val_t t = 0;
72
        for (auto e2 : out_edges_range(n, g))
73
        {
74
            auto n2 = target(e2, g);
75
76
            if (mark[n2] > 0)
                t += eweight[e2];
77
        }
78
79
        triangles += t * eweight[e];
        mark[n] = m;
80
    }
81

82
    for (auto n : adjacent_vertices_range(v, g))
83
        mark[n] = 0;
84

85
    if (graph_tool::is_directed(g))
86
        return make_pair(val_t(triangles), val_t((k * (k - 1))));
87
    else
88
        return make_pair(val_t(triangles / 2), val_t((k * (k - 1)) / 2));
89
90
91
92
93
94
}


// retrieves the global clustering coefficient
struct get_global_clustering
{
95
96
    template <class Graph, class EWeight>
    void operator()(const Graph& g, EWeight eweight, double& c, double& c_err) const
97
    {
98
99
100
        typedef typename property_traits<EWeight>::value_type val_t;
        val_t triangles = 0, n = 0;
        vector<val_t> mask(num_vertices(g), 0);
101
        vector<std::pair<val_t, val_t>> ret(num_vertices(g));
102

Tiago Peixoto's avatar
Tiago Peixoto committed
103
104
105
106
107
108
        #pragma omp parallel if (num_vertices(g) > OPENMP_MIN_THRESH) \
            firstprivate(mask) reduction(+:triangles, n)
        parallel_vertex_loop_no_spawn
                (g,
                 [&](auto v)
                 {
109
                     auto temp = get_triangles(v, eweight, mask, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
110
111
112
                     triangles += temp.first;
                     n += temp.second;
                 });
113
        c = double(triangles) / n;
114
115
116

        // "jackknife" variance
        c_err = 0.0;
117
        double cerr = 0.0;
118
119
        #pragma omp parallel if (num_vertices(g) > OPENMP_MIN_THRESH)   \
            reduction(+:cerr)
Tiago Peixoto's avatar
Tiago Peixoto committed
120
121
122
123
        parallel_vertex_loop_no_spawn
                (g,
                 [&](auto v)
                 {
124
125
                     auto cl = double(triangles - ret[v].first) /
                         (n - ret[v].second);
Tiago Peixoto's avatar
Tiago Peixoto committed
126
127
                     cerr += power(c - cl, 2);
                 });
128

129
        c_err = sqrt(cerr);
130
131
132
133
134
135
    }
};

// sets the local clustering coefficient to a property
struct set_clustering_to_property
{
136
137
    template <class Graph, class EWeight, class ClustMap>
    void operator()(const Graph& g, EWeight eweight, ClustMap clust_map) const
138
    {
139
140
        typedef typename property_traits<EWeight>::value_type val_t;
        vector<val_t> mask(num_vertices(g), false);
141

Tiago Peixoto's avatar
Tiago Peixoto committed
142
143
144
145
146
147
        #pragma omp parallel if (num_vertices(g) > OPENMP_MIN_THRESH) \
            firstprivate(mask)
        parallel_vertex_loop_no_spawn
            (g,
             [&](auto v)
             {
148
                 auto triangles = get_triangles(v, eweight, mask, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
149
150
151
                 double clustering = (triangles.second > 0) ?
                     double(triangles.first)/triangles.second :
                     0.0;
152
                 clust_map[v] = clustering;
Tiago Peixoto's avatar
Tiago Peixoto committed
153
             });
154
    }
155

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

167
} //graph-tool namespace
168
169

#endif // GRAPH_CLUSTERING_HH