graph_trust_transitivity.hh 7.78 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-2017 Tiago de Paula Peixoto <tiago@skewed.de>
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//
// 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_TRUST_TRANSITIVITY_HH
#define GRAPH_TRUST_TRANSITIVITY_HH

#include "graph.hh"
#include "graph_filtering.hh"
#include "graph_util.hh"

#include <algorithm>

#include <boost/graph/dijkstra_shortest_paths.hpp>

#include <iostream>

namespace graph_tool
{
using namespace std;
using namespace boost;


struct stop_search {}; // exception to be thrown to stop search

template <class SourceMap, class WeightMap>
class source_counter:
    public boost::dijkstra_visitor<null_visitor>
{
public:
    source_counter(SourceMap source_map, WeightMap weight_map, size_t n_sources)
        : _source_map(source_map), _weight_map(weight_map),
          _n_sources(n_sources) {}

    template <class Graph>
    void examine_vertex(typename graph_traits<Graph>::vertex_descriptor u,
50
                        Graph&)
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
    {
        // stop if all sources are found
        if (_source_map[u])
        {
            _n_sources--;
            if (_n_sources == 0)
                throw stop_search();
        }
    }

private:
    SourceMap _source_map;
    WeightMap _weight_map;
    size_t _n_sources;
};

struct dist_compare
{
    template <class Type1, class Type2>
    bool operator()(const Type1& d1, const Type2& d2) const
    {
        return d1 > d2; // we want trust paths with _maximum_ "distance"
    }
};

struct dist_combine
{
    template <class DistType, class WeightType>
    DistType operator()(const DistType& d, const WeightType& w) const
    {
81
        return DistType(d * w);
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
    }
};

// predicate to filter a single vertex from the graph
struct filter_vertex_pred
{
    filter_vertex_pred() {}
    filter_vertex_pred(size_t v): _v(v) {}
    template <class Vertex>
    bool operator()(const Vertex& v) const { return v != _v; }
    size_t _v;
};

struct get_trust_transitivity
{
97
    template <class Graph, class VertexIndex, class TrustMap,
98
              class InferredTrustMap>
99
100
    void operator()(Graph& g, VertexIndex vertex_index, int64_t source,
                    int64_t target, TrustMap c, InferredTrustMap t) const
101
102
103
104
105
    {
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
        typedef typename
            property_traits<InferredTrustMap>::value_type::value_type t_type;

Tiago Peixoto's avatar
Tiago Peixoto committed
106
        size_t N = (target == -1) ? num_vertices(g) : target + 1;
107
108
109
110
111
112
113

        parallel_vertex_loop
            (g,
             [&](auto v)
             {
                 t[v].resize((source == -1 && target == -1) ? N : 1);
             });
114

Tiago Peixoto's avatar
Tiago Peixoto committed
115
116
        #pragma omp parallel for if (num_vertices(g) > OPENMP_MIN_THRESH)
        for (size_t i = (target == -1) ? 0 : target; i < N; ++i)
117
118
        {
            vertex_t tgt = vertex(i, g);
119
            if (!is_valid_vertex(tgt, g))
120
                continue;
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

            // mark the sources
            typedef unchecked_vector_property_map<uint8_t, VertexIndex>
                source_map_t;
            source_map_t source_map(vertex_index, num_vertices(g));

            typename in_edge_iteratorS<Graph>::type e, e_end;
            for (tie(e, e_end) = in_edge_iteratorS<Graph>::get_edges(tgt, g);
                 e != e_end; ++e)
                source_map[boost::source(*e,g)] = true;

            // filter vertex w out of the graph
            typedef filtered_graph<Graph, boost::keep_all, filter_vertex_pred>
                fg_t;
            fg_t fg(g, boost::keep_all(), filter_vertex_pred(tgt));

            // distance map (target weight map)
            typedef unchecked_vector_property_map<t_type, VertexIndex>
                dist_map_t;
            dist_map_t dist_map(vertex_index, num_vertices(g));

142
143
144
145
146
            // color map
            typedef unchecked_vector_property_map<default_color_type, VertexIndex>
                color_map_t;
            color_map_t color_map(vertex_index, num_vertices(g));

147
148
149
150
151
152
153
154
155
156
157
158
            if (source != -1)
            {
                vertex_t src = vertex(source, g);

                // compute the targets weights
                try
                {
                    size_t k = in_degreeS()(tgt, g);
                    source_counter<source_map_t,dist_map_t>
                        visitor(source_map, dist_map, k);
                    dijkstra_shortest_paths(fg, src, weight_map(c).
                                            vertex_index_map(vertex_index).
159
                                            color_map(color_map).
160
161
162
163
164
165
166
167
168
169
170
                                            distance_map(dist_map).
                                            distance_compare(dist_compare()).
                                            distance_combine(dist_combine()).
                                            distance_inf(t_type(0)).
                                            distance_zero(t_type(1)).
                                            visitor(visitor));
                }
                catch (const stop_search&) {}

                // compute the target's trust
                t_type sum_w = 0, avg = 0;
171
                for (auto e : in_edges_range(tgt, g))
172
                {
173
                    t_type weight = dist_map[boost::source(e, g)];
174
                    sum_w += weight;
175
                    avg += c[e]*weight*weight;
176
177
178
179
180
181
182
183
184
185
186
187
188
189
                }
                if (sum_w > 0)
                    t[tgt][0] = avg/sum_w;
                if (tgt == src)
                    t[tgt][0] = 1.0;
            }
            else
            {
                typedef typename
                    mpl::if_<typename is_directed::apply<Graph>::type,
                             reverse_graph<fg_t>,
                             fg_t>::type rg_t;
                rg_t rg(fg);
                dist_map_t sum_w(vertex_index, num_vertices(g));
190
                for (auto e : in_edges_range(tgt, g))
191
192
193
                {
                    // compute the weights to all sources
                    dijkstra_shortest_paths
194
                        (rg, boost::source(e, g), weight_map(c).
195
                         vertex_index_map(vertex_index).
196
                         color_map(color_map).
197
198
199
200
201
202
                         distance_map(dist_map).
                         distance_compare(dist_compare()).
                         distance_combine(dist_combine()).
                         distance_inf(t_type(0)).
                         distance_zero(t_type(1)));

203
204
205
206
207
208
209
210
211
                    parallel_vertex_loop
                        (g,
                         [&](auto src)
                         {
                             t_type weight = dist_map[src];
                             sum_w[src] += weight;
                             size_t tidx = (target == -1) ? vertex_index[tgt] : 0;
                             t[src][tidx] += c[e]*weight*weight;
                         });
212
213
                }

214
215
216
217
218
219
220
221
222
223
                parallel_vertex_loop
                    (g,
                     [&](auto src)
                     {
                         size_t tidx = (target == -1) ? vertex_index[tgt] : 0;
                         if (sum_w[src] > 0)
                             t[src][tidx] /= sum_w[src];
                         if (src == tgt)
                             t[src][tidx] = 1.0;
                     });
224
225
226
227
228
229
230
231
            }
        }
    }
};

}

#endif