| 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. |