graph_clustering.hh 5.44 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2007-2011 Tiago de Paula Peixoto <tiago@skewed.de>
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//
// 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.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef GRAPH_CLUSTERING_HH
#define GRAPH_CLUSTERING_HH

21
22
23
24
25
#if (GCC_VERSION >= 40400)
#   include <tr1/unordered_set>
#else
#   include <boost/tr1/unordered_set.hpp>
#endif
26
27
28
29
30
31
32
33
#include <boost/mpl/if.hpp>

namespace graph_tool
{
using namespace boost;

// calculates the number of triangles to which v belongs
template <class Graph>
34
pair<int,int>
35
36
get_triangles(typename graph_traits<Graph>::vertex_descriptor v, const Graph &g)
{
37
    tr1::unordered_set<typename graph_traits<Graph>::vertex_descriptor>
38
        neighbour_set1, neighbour_set2, neighbour_set3;
39

40
    size_t triangles = 0, k = 0;
41

42
43
44
45
46
47
48
49
50
51
    typename graph_traits<Graph>::adjacency_iterator n1_begin, n1_end, n1;
    tie(n1_begin, n1_end) = adjacent_vertices(v, g);
    for (n1 = n1_begin; n1 != n1_end; ++n1)
    {
        if (*n1 == v) // no self-loops
            continue;
        if (neighbour_set1.find(*n1) != neighbour_set1.end())
            continue;
        else
            neighbour_set1.insert(*n1);
52

53
54
55
56
57
58
59
60
61
62
        typename graph_traits<Graph>::adjacency_iterator n2_begin, n2_end, n2;
        tie(n2_begin, n2_end) = adjacent_vertices(*n1, g);
        for (n2 = n2_begin; n2 != n2_end; ++n2)
        {
            if (*n2 == *n1) // no self-loops
                continue;
            if (neighbour_set2.find(*n2) != neighbour_set2.end())
                continue;
            else
                neighbour_set2.insert(*n2);
63
64

            typename graph_traits<Graph>::adjacency_iterator
65
66
67
68
69
70
71
72
73
74
                n3_begin, n3_end, n3;
            tie(n3_begin, n3_end) = adjacent_vertices(*n2, g);
            for (n3 = n3_begin; n3 != n3_end; ++n3)
            {
                if (*n3 == *n2) // no self-loops
                    continue;
                if (neighbour_set3.find(*n3) != neighbour_set3.end())
                    continue;
                else
                    neighbour_set3.insert(*n3);
75

76
                if (*n3 == v) //found a triangle
77
                    triangles++;
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
            }
            neighbour_set3.clear();
        }
        neighbour_set2.clear();
        k++;
    }
    neighbour_set1.clear();
    return make_pair(triangles/2,(k*(k-1))/2);
}


// retrieves the global clustering coefficient
struct get_global_clustering
{
    template <class Graph>
93
    void operator()(const Graph& g, double& c, double& c_err) const
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
    {
        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) \
            schedule(dynamic) reduction(+:triangles)
        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);
109
            triangles += temp.first;
110
111
112
113
114
115
            n += temp.second;
        }
        c = double(triangles)/n;

        // "jackknife" variance
        c_err = 0.0;
116

117
        #pragma omp parallel for default(shared) private(i,temp) \
Tiago Peixoto's avatar
Tiago Peixoto committed
118
            schedule(dynamic)
119
120
121
122
123
124
125
126
127
        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);
            double cl = double(triangles - temp.first)/(n - temp.second);

Tiago Peixoto's avatar
Tiago Peixoto committed
128
            #pragma omp atomic
129
            c_err += (c - cl)*(c - cl);
130
131
132
133
134
135
136
137
138
        }
        c_err = sqrt(c_err);
    }
};

// sets the local clustering coefficient to a property
struct set_clustering_to_property
{
    template <class Graph, class ClustMap>
139
    void operator()(const Graph& g, ClustMap clust_map) const
140
141
142
    {
        typename get_undirected_graph<Graph>::type ug(g);
        int i, N = num_vertices(g);
143

144
145
146
147
148
149
        #pragma omp parallel for default(shared) private(i) schedule(dynamic)
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
150

151
152
153
154
            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;
155

156
157
158
159
160
161
            #pragma omp critical
            {
                clust_map[v] = clustering;
            }
        }
    }
162

163
164
165
166
167
168
169
170
171
172
173
    template <class Graph>
    struct get_undirected_graph
    {
        typedef typename mpl::if_
            < is_convertible<typename graph_traits<Graph>::directed_category,
                             directed_tag>,
              const UndirectedAdaptor<Graph>,
              const Graph& >::type type;
    };
};

174
} //graph-tool namespace
175
176

#endif // GRAPH_CLUSTERING_HH