2
Copyright 2008-2010 Gephi
3
Authors : Patick J. McSweeney <pjmcswee@syr.edu>, Sebastien Heymann <seb@gephi.org>
4
Website : http://www.gephi.org
6
This file is part of Gephi.
8
Gephi is free software: you can redistribute it and/or modify
9
it under the terms of the GNU Affero General Public License as
10
published by the Free Software Foundation, either version 3 of the
11
License, or (at your option) any later version.
13
Gephi is distributed in the hope that it will be useful,
14
but WITHOUT ANY WARRANTY; without even the implied warranty of
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16
GNU Affero General Public License for more details.
18
You should have received a copy of the GNU Affero General Public License
19
along with Gephi. If not, see <http://www.gnu.org/licenses/>.
21
package org.gephi.statistics.plugin;
24
import java.io.IOException;
25
import org.gephi.data.attributes.api.AttributeModel;
26
import org.gephi.statistics.spi.Statistics;
27
import org.gephi.graph.api.*;
28
import org.gephi.utils.TempDirUtils;
29
import org.gephi.utils.TempDirUtils.TempDir;
30
import org.gephi.utils.longtask.spi.LongTask;
31
import org.gephi.utils.progress.Progress;
32
import org.gephi.utils.progress.ProgressTicket;
33
import org.jfree.chart.ChartFactory;
34
import org.jfree.chart.ChartRenderingInfo;
35
import org.jfree.chart.ChartUtilities;
36
import org.jfree.chart.JFreeChart;
37
import org.jfree.chart.entity.StandardEntityCollection;
38
import org.jfree.chart.plot.PlotOrientation;
39
import org.jfree.chart.plot.XYPlot;
40
import org.jfree.chart.renderer.xy.XYLineAndShapeRenderer;
41
import org.jfree.data.xy.XYSeries;
42
import org.jfree.data.xy.XYSeriesCollection;
43
import org.openide.util.Exceptions;
44
import org.openide.util.Lookup;
47
* This class measures how closely the degree distribution of a
48
* network follows a power-law scale. An alpha value between 2 and 3
49
* implies a power law.
52
public class DegreeDistribution implements Statistics, LongTask {
54
/** The combined In/Out-degree distribution. */
55
private double[][] combinedDistribution;
56
/** The In-degree distribution. */
57
private double[][] inDistribution;
58
/** The out-degree distribution. */
59
private double[][] outDistribution;
60
/** Remember if the metric has been canceled. */
61
private boolean isCanceled;
62
/** The progress meter for this metric. */
63
private ProgressTicket progress;
64
/** Indicates if this network should be directed or undirected.*/
65
private boolean isDirected;
66
/** The powerlaw value for the combined in/out-degree of this network. */
67
private double combinedAlpha;
68
/** The powerlaw value for the in-degree of this network. */
69
private double inAlpha;
70
/** The powerlaw value for the out-degree of this network. */
71
private double outAlpha;
72
/** The powerlaw value for the combined in/out-degree of this network. */
73
private double combinedBeta;
74
/** The powerlaw value for the in-degree of this network. */
75
private double inBeta;
76
/** The powerlaw value for the out-degree of this network. */
77
private double outBeta;
79
public DegreeDistribution() {
80
GraphController graphController = Lookup.getDefault().lookup(GraphController.class);
81
if (graphController != null && graphController.getModel() != null) {
82
isDirected = graphController.getModel().isDirected();
87
* @param isDirected Indicates the metric's interpretation of this network.
89
public void setDirected(boolean isDirected) {
90
this.isDirected = isDirected;
93
public boolean isDirected() {
98
* @return The combined in/out-degree power law value for this network.
100
public double getCombinedPowerLaw() {
101
return this.combinedAlpha;
105
* @return The combined in/out-degree power law value for this network.
107
public double getInPowerLaw() {
112
* @return The combined in/out-degree power law value for this network.
114
public double getOutPowerLaw() {
115
return this.outAlpha;
119
* Calculates the degree distribution for this network.
120
* Either a combined degree distribution or separate
121
* in-degree distribution and out-degree distribution
122
* is calculated based on the mDirected variable.
126
public void execute(GraphModel graphModel, AttributeModel attributeModel) {
127
//Get the graph from the graphController, based
128
//on the mDirected variable.
129
HierarchicalGraph graph;
131
graph = graphModel.getHierarchicalDirectedGraphVisible();
133
graph = graphModel.getHierarchicalUndirectedGraphVisible();
135
execute(graph, attributeModel);
138
public void execute(HierarchicalGraph graph, AttributeModel attributeModel) {
139
//Mark this as not yet canceled.
145
Progress.start(progress, graph.getNodeCount());
148
//Consider the in and out degree of every node
150
inDistribution = new double[2][2 * graph.getNodeCount()];
151
outDistribution = new double[2][2 * graph.getNodeCount()];
153
combinedDistribution = new double[2][2 * graph.getNodeCount()];
158
for (Node node : graph.getNodes()) {
160
int inDegree = ((HierarchicalDirectedGraph) graph).getTotalInDegree(node);
161
int outDegree = ((HierarchicalDirectedGraph) graph).getTotalOutDegree(node);
162
inDistribution[1][inDegree]++;
163
outDistribution[1][outDegree]++;
164
inDistribution[0][inDegree] = inDegree;
165
outDistribution[0][outDegree] = outDegree;
167
int combinedDegree = ((HierarchicalUndirectedGraph) graph).getTotalDegree(node);
168
combinedDistribution[1][combinedDegree]++;
169
combinedDistribution[0][combinedDegree] = combinedDegree;
171
Progress.progress(progress, nodeCount);
174
graph.readUnlockAll();
182
double[] inFit = new double[2];
183
double[] outFit = new double[2];
184
leastSquares(inDistribution[1], inFit);
185
leastSquares(outDistribution[1], outFit);
188
outAlpha = outFit[1];
191
double[] fit = new double[2];
192
leastSquares(combinedDistribution[1], fit);
193
combinedAlpha = fit[1];
194
combinedBeta = fit[0];
199
* Fits the logarithm distribution/degree to a straight line of the form:
200
* a + b *x which is then interpreted as a*x^y in the non-logarithmic scale
202
* @param dist The distribution of node degrees to fit to a logarithmized straight line
204
* @return An array of 2 doubles
208
* For more see Wolfram Least Squares Fitting
210
public void leastSquares(double[] dist, double[] res) {
211
//Vararibles to compute
216
//Compute the average log(x) value when for positive (>0) values
220
for (int i = 1; i < dist.length; i++) {
223
avgY += Math.log(dist[i]);
235
//compute the variance of log(x)
236
for (int i = 1; i < dist.length; i++) {
238
SSxx += Math.pow(Math.log(i) - avgX, 2);
239
//SSyy += Math.pow(Math.log(dist[i]) - avgY, 2);
240
SSxy += (Math.log(i) - avgX) * (Math.log(dist[i]) - avgY);
244
//Compute and return the results
245
res[0] = SSxy / SSxx;
246
res[1] = avgY - res[0] * avgX;
250
* @return A String report based on the interpretation of the network.
252
public String getReport() {
253
return (isDirected) ? getDirectedReport() : getUndirectedReport();
258
* @return The directed version of the report.
260
private String getDirectedReport() {
262
XYSeries inSeries2 = new XYSeries("Series 2");
263
for (int i = 1; i < inDistribution[1].length; i++) {
264
if (inDistribution[1][i] > 0) {
265
inSeries2.add((Math.log(inDistribution[0][i]) / Math.log(Math.E)), (Math.log(inDistribution[1][i]) / Math.log(Math.E)));
266
inMax = (float) Math.max((Math.log(inDistribution[0][i]) / Math.log(Math.E)), inMax);
269
double inA = inAlpha;
272
String inImageFile = "";
273
String outImageFile = "";
276
XYSeries inSeries1 = new XYSeries(inAlpha + " ");
277
inSeries1.add(0, inA);
278
inSeries1.add(inMax, inA + inB * inMax);
280
XYSeriesCollection inDataset = new XYSeriesCollection();
281
inDataset.addSeries(inSeries1);
282
inDataset.addSeries(inSeries2);
284
JFreeChart inChart = ChartFactory.createXYLineChart(
285
"In-Degree Distribution",
289
PlotOrientation.VERTICAL,
293
XYPlot inPlot = (XYPlot) inChart.getPlot();
294
XYLineAndShapeRenderer inRenderer = new XYLineAndShapeRenderer();
295
inRenderer.setSeriesLinesVisible(0, true);
296
inRenderer.setSeriesShapesVisible(0, false);
297
inRenderer.setSeriesLinesVisible(1, false);
298
inRenderer.setSeriesShapesVisible(1, true);
299
inRenderer.setSeriesShape(1, new java.awt.geom.Ellipse2D.Double(0, 0, 1, 1));
300
inPlot.setBackgroundPaint(java.awt.Color.WHITE);
301
inPlot.setDomainGridlinePaint(java.awt.Color.GRAY);
302
inPlot.setRangeGridlinePaint(java.awt.Color.GRAY);
304
inPlot.setRenderer(inRenderer);
306
final ChartRenderingInfo info = new ChartRenderingInfo(new StandardEntityCollection());
309
TempDir tempDir = TempDirUtils.createTempDir();
310
final String fileName = "inDistribution.png";
311
final File file1 = tempDir.createFile(fileName);
312
inImageFile = "<IMG SRC=\"file:" + file1.getAbsolutePath() + "\" " + "WIDTH=\"600\" HEIGHT=\"400\" BORDER=\"0\" USEMAP=\"#chart\"></IMG>";
313
ChartUtilities.saveChartAsPNG(file1, inChart, 600, 400, info);
317
XYSeries outSeries2 = new XYSeries("Series 2");
318
for (int i = 1; i < outDistribution[1].length; i++) {
319
if (outDistribution[1][i] > 0) {
320
outSeries2.add((Math.log(outDistribution[0][i]) / Math.log(Math.E)), (Math.log(outDistribution[1][i]) / Math.log(Math.E)));
321
outMax = (float) Math.max((Math.log(outDistribution[0][i]) / Math.log(Math.E)), outMax);
324
double outA = outAlpha;
325
double outB = outBeta;
328
XYSeries outSeries1 = new XYSeries(outAlpha + " ");
329
outSeries1.add(0, outA);
330
outSeries1.add(outMax, outA + outB * outMax);
332
XYSeriesCollection outDataset = new XYSeriesCollection();
333
outDataset.addSeries(outSeries1);
334
outDataset.addSeries(outSeries2);
336
JFreeChart outchart = ChartFactory.createXYLineChart(
337
"Out-Degree Distribution",
341
PlotOrientation.VERTICAL,
345
XYPlot outPlot = (XYPlot) outchart.getPlot();
346
XYLineAndShapeRenderer outRenderer = new XYLineAndShapeRenderer();
347
outRenderer.setSeriesLinesVisible(0, true);
348
outRenderer.setSeriesShapesVisible(0, false);
349
outRenderer.setSeriesLinesVisible(1, false);
350
outRenderer.setSeriesShapesVisible(1, true);
351
outRenderer.setSeriesShape(1, new java.awt.geom.Ellipse2D.Double(0, 0, 1, 1));
352
outPlot.setBackgroundPaint(java.awt.Color.WHITE);
353
outPlot.setDomainGridlinePaint(java.awt.Color.GRAY);
354
outPlot.setRangeGridlinePaint(java.awt.Color.GRAY);
356
outPlot.setRenderer(outRenderer);
358
final ChartRenderingInfo info2 = new ChartRenderingInfo(new StandardEntityCollection());
359
final String fileName2 = "outDistribution.png";
360
final File file2 = tempDir.createFile(fileName2);
361
outImageFile = "<IMG SRC=\"file:" + file2.getAbsolutePath() + "\" " + "WIDTH=\"600\" HEIGHT=\"400\" BORDER=\"0\" USEMAP=\"#chart\"></IMG>";
362
ChartUtilities.saveChartAsPNG(file2, outchart, 600, 400, info2);
363
} catch (IOException e) {
364
Exceptions.printStackTrace(e);
370
String report = "<HTML> <BODY> <h1>Degree Distribution Metric Report </h1> "
373
+ "<h2> Parameters: </h2>"
374
+ "Network Interpretation: " + (isDirected ? "directed" : "undirected") + "<br>"
375
+ "<br> <h2> Results: </h2>"
376
+ "In-Degree Power Law: -" + inAlpha + "\n <BR>"
377
+ inImageFile + "<br>Out-Degree Power Law: -" + outAlpha + "\n <BR>"
378
+ outImageFile + "</BODY> </HTML>";
386
* @return The undirected version of this report.
388
private String getUndirectedReport() {
390
XYSeries series2 = new XYSeries("Series 2");
391
for (int i = 1; i < combinedDistribution[1].length; i++) {
392
if (combinedDistribution[1][i] > 0) {
393
series2.add((Math.log(combinedDistribution[0][i]) / Math.log(Math.E)), (Math.log(combinedDistribution[1][i]) / Math.log(Math.E)));
394
max = (float) Math.max((Math.log(combinedDistribution[0][i]) / Math.log(Math.E)), max);
397
double a = combinedAlpha;
398
double b = combinedBeta;
401
XYSeries series1 = new XYSeries(combinedAlpha + " ");
403
series1.add(max, a + b * max);
405
XYSeriesCollection dataset = new XYSeriesCollection();
406
dataset.addSeries(series1);
407
dataset.addSeries(series2);
409
JFreeChart chart = ChartFactory.createXYLineChart(
410
"Degree Distribution",
414
PlotOrientation.VERTICAL,
418
XYPlot plot = (XYPlot) chart.getPlot();
419
XYLineAndShapeRenderer renderer = new XYLineAndShapeRenderer();
420
renderer.setSeriesLinesVisible(0, true);
421
renderer.setSeriesShapesVisible(0, false);
422
renderer.setSeriesLinesVisible(1, false);
423
renderer.setSeriesShapesVisible(1, true);
424
renderer.setSeriesShape(1, new java.awt.geom.Ellipse2D.Double(0, 0, 1, 1));
425
plot.setBackgroundPaint(java.awt.Color.WHITE);
426
plot.setDomainGridlinePaint(java.awt.Color.GRAY);
427
plot.setRangeGridlinePaint(java.awt.Color.GRAY);
429
plot.setRenderer(renderer);
432
String imageFile = "";
434
final ChartRenderingInfo info = new ChartRenderingInfo(new StandardEntityCollection());
435
TempDir tempDir = TempDirUtils.createTempDir();
436
final String fileName = "distribution.png";
437
final File file1 = tempDir.createFile(fileName);
438
imageFile = "<IMG SRC=\"file:" + file1.getAbsolutePath() + "\" " + "WIDTH=\"600\" HEIGHT=\"400\" BORDER=\"0\" USEMAP=\"#chart\"></IMG>";
439
ChartUtilities.saveChartAsPNG(file1, chart, 600, 400, info);
441
} catch (IOException e) {
442
System.out.println(e.toString());
446
String report = "<HTML> <BODY> <h1>Degree Distribution Metric Report </h1> "
449
+ "<h2> Parameters: </h2>"
450
+ "Network Interpretation: " + (isDirected ? "directed" : "undirected") + "<br>"
451
+ "<br> <h2> Results: </h2>"
452
+ "Degree Power Law: -" + combinedAlpha + "\n <BR>"
453
+ imageFile + "</BODY> </HTML>";
458
* @return Indicates that the metric canceled flag was set.
460
public boolean cancel() {
466
* @param progressTicket Sets the progress meter for the metric.
468
public void setProgressTicket(ProgressTicket pProgressTicket) {
469
progress = pProgressTicket;
added
removed
StatisticsPlugin/src/org/gephi/statistics/plugin/DegreeDistribution.java
