Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University | |
3 | * of California | |
4 | * All rights reserved. | |
5 | * | |
6 | * This software is open-source under the BSD license; see either | |
7 | * "license.txt" or | |
8 | * http://jung.sourceforge.net/license.txt for a description. | |
9 | */ | |
10 | package edu.uci.ics.jung.algorithms.metrics; | |
11 | ||
12 | import java.util.HashSet; | |
13 | import java.util.Iterator; | |
14 | import java.util.Set; | |
15 | ||
16 | import org.apache.commons.collections.CollectionUtils; | |
17 | ||
18 | import edu.uci.ics.jung.graph.DirectedGraph; | |
19 | import edu.uci.ics.jung.graph.Vertex; | |
20 | import edu.uci.ics.jung.graph.decorators.Indexer; | |
21 | ||
22 | /** | |
23 | * TriadicCensus is a standard social network tool that counts, for each of the | |
24 | * different possible configurations of three vertices, the number of times | |
25 | * that that configuration occurs in the given graph. | |
26 | * This may then be compared to the set of expected counts for this particular | |
27 | * graph or to an expected sample. This is often used in p* modeling. | |
28 | * <p> | |
29 | * To use this class, | |
30 | * <pre> | |
31 | * long[] triad_counts = TriadicCensus(dg); | |
32 | * </pre> | |
33 | * where <code>dg</code> is a <code>DirectedGraph</code>. | |
34 | * ith element of the array (for i in [1,16]) is the number of | |
35 | * occurrences of the corresponding triad type. | |
36 | * (The 0th element is not meaningful; this array is effectively 1-based.) | |
37 | * To get the name of the ith triad (e.g. "003"), | |
38 | * look at the global constant array c.TRIAD_NAMES[i] | |
39 | * <p> | |
40 | * Triads are named as | |
41 | * (number of pairs that are mutually tied) | |
42 | * (number of pairs that are one-way tied) | |
43 | * (number of non-tied pairs) | |
44 | * in the triple. Since there are be only three pairs, there is a finite | |
45 | * set of these possible triads. | |
46 | * <p> | |
47 | * In fact, there are exactly 16, conventionally sorted by the number of | |
48 | * realized edges in the triad: | |
49 | * <table> | |
50 | * <tr><th>Number</th> <th>Configuration</th> <th>Notes</th></tr> | |
51 | * <tr><td>1</td><td>003</td><td>The empty triad</td></tr> | |
52 | * <tr><td>2</td><td>012</td><td></td></tr> | |
53 | * <tr><td>3</td><td>102</td><td></td></tr> | |
54 | * <tr><td>4</td><td>021D</td><td>"Down": the directed edges point away</td></tr> | |
55 | * <tr><td>5</td><td>021U</td><td>"Up": the directed edges meet</td></tr> | |
56 | * <tr><td>6</td><td>021C</td><td>"Circle": one in, one out</td></tr> | |
57 | * <tr><td>7</td><td>111D</td><td>"Down": 021D but one edge is mutual</td></tr> | |
58 | * <tr><td>8</td><td>111U</td><td>"Up": 021U but one edge is mutual</td></tr> | |
59 | * <tr><td>9</td><td>030T</td><td>"Transitive": two point to the same vertex</td></tr> | |
60 | * <tr><td>10</td><td>030C</td><td>"Circle": A->B->C->A</td></tr> | |
61 | * <tr><td>11</td><td>201</td><td></td></tr> | |
62 | * <tr><td>12</td><td>120D</td><td>"Down": 021D but the third edge is mutual</td></tr> | |
63 | * <tr><td>13</td><td>120U</td><td>"Up": 021U but the third edge is mutual</td></tr> | |
64 | * <tr><td>14</td><td>120C</td><td>"Circle": 021C but the third edge is mutual</td></tr> | |
65 | * <tr><td>15</td><td>210</td><td></td></tr> | |
66 | * <tr><td>16</td><td>300</td><td>The complete</td></tr> | |
67 | * </table> | |
68 | * <p> | |
69 | * This implementation takes O( m ), m is the number of edges in the graph. | |
70 | * <br> | |
71 | * It is based on | |
72 | * <a href="http://vlado.fmf.uni-lj.si/pub/networks/doc/triads/triads.pdf"> | |
73 | * A subquadratic triad census algorithm for large sparse networks | |
74 | * with small maximum degree</a> | |
75 | * Vladimir Batagelj and Andrej Mrvar, University of Ljubljana | |
76 | * Published in Social Networks. | |
77 | * @author Danyel Fisher | |
78 | * | |
79 | */ | |
80 | 0 | public class TriadicCensus { |
81 | ||
82 | // NOTE THAT THIS RETURNS STANDARD 1-16 COUNT! | |
83 | ||
84 | // and their types | |
85 | 1 | public static final String[] TRIAD_NAMES = { "N/A", "003", "012", "102", "021D", |
86 | "021U", "021C", "111D", "111U", "030T", "030C", "201", "120D", | |
87 | "120U", "120C", "210", "300" }; | |
88 | ||
89 | 1 | public static final int MAX_TRIADS = TRIAD_NAMES.length; |
90 | ||
91 | /** | |
92 | * Returns an array whose ith element (for i in [1,16]) is the number of | |
93 | * occurrences of the corresponding triad type in <code>g</code>. | |
94 | * (The 0th element is not meaningful; this array is effectively 1-based.) | |
95 | * | |
96 | * @param g | |
97 | */ | |
98 | public static long[] getCounts(DirectedGraph g) | |
99 | { | |
100 | 8 | long[] count = new long[MAX_TRIADS]; |
101 | ||
102 | 8 | Indexer id = Indexer.getIndexer(g); |
103 | ||
104 | // apply algorithm to each edge, one at at time | |
105 | 28 | for (int i_v = 0; i_v < g.numVertices(); i_v++) { |
106 | 20 | Vertex v = (Vertex) id.getVertex(i_v); |
107 | 20 | for (Iterator iter = v.getNeighbors().iterator(); iter.hasNext();) { |
108 | 26 | int triType = -1; |
109 | 26 | Vertex u = (Vertex) iter.next(); |
110 | 26 | if (id.getIndex(u) <= i_v) |
111 | 13 | continue; |
112 | 13 | Set neighbors = new HashSet(CollectionUtils.union(u |
113 | .getNeighbors(), v.getNeighbors())); | |
114 | 13 | neighbors.remove(u); |
115 | 13 | neighbors.remove(v); |
116 | 13 | if (u.isSuccessorOf(v) && v.isSuccessorOf(u)) { |
117 | 4 | triType = 3; |
118 | } else { | |
119 | 9 | triType = 2; |
120 | } | |
121 | 13 | count[triType] += g.numVertices() - neighbors.size() - 2; |
122 | 13 | for (Iterator iterator = neighbors.iterator(); iterator |
123 | 30 | .hasNext();) { |
124 | 17 | Vertex w = (Vertex) iterator.next(); |
125 | 17 | if (shouldCount(id, u, v, w)) { |
126 | 7 | count [ triType ( triCode(u, v, w) ) ] ++; |
127 | } | |
128 | } | |
129 | } | |
130 | } | |
131 | 8 | int sum = 0; |
132 | 128 | for (int i = 2; i <= 16; i++) { |
133 | 120 | sum += count[i]; |
134 | } | |
135 | 8 | int n = g.numVertices(); |
136 | 8 | count[1] = n * (n-1) * (n-2) / 6 - sum; |
137 | 8 | return count; |
138 | } | |
139 | ||
140 | /** | |
141 | * This is the core of the technique in the paper. Returns an int from 0 to | |
142 | * 65 based on: WU -> 32 UW -> 16 WV -> 8 VW -> 4 UV -> 2 VU -> 1 | |
143 | * | |
144 | */ | |
145 | public static int triCode(Vertex u, Vertex v, Vertex w) { | |
146 | 10 | int i = 0; |
147 | 10 | i += link( v, u ) ? 1 : 0; |
148 | 10 | i += link( u, v ) ? 2 : 0; |
149 | 10 | i += link( v, w ) ? 4 : 0; |
150 | 10 | i += link( w, v ) ? 8 : 0; |
151 | 10 | i += link( u, w ) ? 16 : 0; |
152 | 10 | i += link( w, u ) ? 32 : 0; |
153 | 10 | return i; |
154 | } | |
155 | ||
156 | protected static boolean link( Vertex a, Vertex b) { | |
157 | 60 | return a.isPredecessorOf(b); |
158 | } | |
159 | ||
160 | ||
161 | /** | |
162 | * Simply returns the triCode. | |
163 | * @param triCode | |
164 | * @return | |
165 | */ | |
166 | public static int triType( int triCode ) { | |
167 | 10 | return codeToType[ triCode ]; |
168 | } | |
169 | ||
170 | /** | |
171 | * For debugging purposes, this is copied straight out of the paper which | |
172 | * means that they refer to triad types 1-16. | |
173 | */ | |
174 | 1 | protected static final int[] codeToType = { 1, 2, 2, 3, 2, 4, 6, 8, 2, 6, 5, 7, 3, 8, |
175 | 7, 11, 2, 6, 4, 8, 5, 9, 9, 13, 6, 10, 9, 14, 7, 14, 12, 15, 2, 5, | |
176 | 6, 7, 6, 9, 10, 14, 4, 9, 9, 12, 8, 13, 14, 15, 3, 7, 8, 11, 7, 12, | |
177 | 14, 15, 8, 14, 13, 15, 11, 15, 15, 16 }; | |
178 | ||
179 | /** | |
180 | * Make sure we have a canonical ordering: Returns true if u < w, or v < w < | |
181 | * u and v doesn't link to w | |
182 | * | |
183 | * @param id | |
184 | * @param u | |
185 | * @param v | |
186 | * @param w | |
187 | * @return | |
188 | */ | |
189 | protected static boolean shouldCount(Indexer id, Vertex u, Vertex v, Vertex w) { | |
190 | 17 | int i_u = id.getIndex(u); |
191 | 17 | int i_w = id.getIndex(w); |
192 | 17 | if (i_u < i_w) |
193 | 5 | return true; |
194 | 12 | int i_v = id.getIndex(v); |
195 | 12 | if ((i_v < i_w) && (i_w < i_u) && (!v.isNeighborOf(w))) |
196 | 2 | return true; |
197 | 10 | return false; |
198 | } | |
199 | ||
200 | // protected void initializeCounts() { | |
201 | // for (int i = 0; i < count.length; i++) { | |
202 | // count[i] = 0; | |
203 | // } | |
204 | // } | |
205 | ||
206 | // /** | |
207 | // * Once you've created a triad, here's the census for that number. A triad | |
208 | // * census looks a little like an array: n elements inside it | |
209 | // * | |
210 | // * @param i | |
211 | // * @return | |
212 | // */ | |
213 | // public long getCount(int i) throws IllegalArgumentException { | |
214 | // if ( i < 1 || i > 16) | |
215 | // throw new IllegalArgumentException("TriType must be 1-16"); | |
216 | // return count[i]; | |
217 | // } | |
218 | ||
219 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |