Coverage details for edu.uci.ics.jung.algorithms.metrics.TriadicCensus

LineHitsSource
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  */
800public class TriadicCensus {
81  
82     // NOTE THAT THIS RETURNS STANDARD 1-16 COUNT!
83  
84     // and their types
851    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  
891    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     {
1008        long[] count = new long[MAX_TRIADS];
101  
1028        Indexer id = Indexer.getIndexer(g);
103  
104         // apply algorithm to each edge, one at at time
10528        for (int i_v = 0; i_v < g.numVertices(); i_v++) {
10620            Vertex v = (Vertex) id.getVertex(i_v);
10720            for (Iterator iter = v.getNeighbors().iterator(); iter.hasNext();) {
10826                int triType = -1;
10926                Vertex u = (Vertex) iter.next();
11026                if (id.getIndex(u) <= i_v)
11113                    continue;
11213                Set neighbors = new HashSet(CollectionUtils.union(u
113                         .getNeighbors(), v.getNeighbors()));
11413                neighbors.remove(u);
11513                neighbors.remove(v);
11613                if (u.isSuccessorOf(v) && v.isSuccessorOf(u)) {
1174                    triType = 3;
118                 } else {
1199                    triType = 2;
120                 }
12113                count[triType] += g.numVertices() - neighbors.size() - 2;
12213                for (Iterator iterator = neighbors.iterator(); iterator
12330                        .hasNext();) {
12417                    Vertex w = (Vertex) iterator.next();
12517                    if (shouldCount(id, u, v, w)) {
1267                        count [ triType ( triCode(u, v, w) ) ] ++;
127                     }
128                 }
129             }
130         }
1318        int sum = 0;
132128        for (int i = 2; i <= 16; i++) {
133120            sum += count[i];
134         }
1358        int n = g.numVertices();
1368        count[1] = n * (n-1) * (n-2) / 6 - sum;
1378        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) {
14610        int i = 0;
14710        i += link( v, u ) ? 1 : 0;
14810        i += link( u, v ) ? 2 : 0;
14910        i += link( v, w ) ? 4 : 0;
15010        i += link( w, v ) ? 8 : 0;
15110        i += link( u, w ) ? 16 : 0;
15210        i += link( w, u ) ? 32 : 0;
15310        return i;
154     }
155  
156     protected static boolean link( Vertex a, Vertex b) {
15760        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 ) {
16710        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      */
1741    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) {
19017        int i_u = id.getIndex(u);
19117        int i_w = id.getIndex(w);
19217        if (i_u < i_w)
1935            return true;
19412        int i_v = id.getIndex(v);
19512        if ((i_v < i_w) && (i_w < i_u) && (!v.isNeighborOf(w)))
1962            return true;
19710        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.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.