public class BarabasiAlbertGenerator extends BaseGenerator
This is a very simple graph generator that generates a graph using the preferential attachment rule defined in the Barabási-Albert model: nodes are generated one by one, and each time attached by one or more edges other nodes. The other nodes are chosen using a biased random selection giving more chance to a node if it has a high degree.
The more this generator is iterated, the more nodes are generated. It can
therefore generate graphs of any size. One node is generated at each call to
nextEvents()
. At each node added at least one new edge is added. The
number of edges added at each step is given by the
getMaxLinksPerStep()
. However by default the generator creates a
number of edges per new node chosen randomly between 1 and
getMaxLinksPerStep()
. To have exactly this number of edges at each
new node, use setExactlyMaxLinksPerStep(boolean)
.
Graph graph = new SingleGraph("Barabàsi-Albert"); // Between 1 and 3 new links per node added. Generator gen = new BarabasiAlbertGenerator(3); // Generate 100 nodes: gen.addSink(graph); gen.begin(); for(int i=0; i<100; i++) { gen.nextEvents(); } gen.end(); graph.display();
SourceBase.ElementType
Modifier and Type | Field and Description |
---|---|
protected Set<Integer> |
connected
Set of indices of nodes connected to the new node
|
protected ArrayList<Integer> |
degrees
Degree of each node.
|
protected boolean |
exactlyMaxLinksPerStep
Does the generator generates exactly
maxLinksPerStep . |
protected int |
maxLinksPerStep
The maximum number of links created when a new node is added.
|
protected int |
sumDeg
The sum of degrees of all nodes
|
protected int |
sumDegRemaining
The sum of degrees of nodes not connected to the new node
|
addEdgeLabels, addNodeLabels, directed, edgeAttributeRange, edgeAttributes, internalGraph, nodeAttributeRange, nodeAttributes, random, randomlyDirected
attrSinks, eltsSinks, eventProcessing, eventQueue, sourceId, sourceTime
Constructor and Description |
---|
BarabasiAlbertGenerator()
New generator.
|
BarabasiAlbertGenerator(int maxLinksPerStep) |
BarabasiAlbertGenerator(int maxLinksPerStep,
boolean exactlyMaxLinksPerStep) |
Modifier and Type | Method and Description |
---|---|
void |
begin()
Start the generator.
|
protected void |
chooseAnotherNode()
Choose randomly one of the remaining nodes
|
void |
end()
Clean degrees.
|
int |
getMaxLinksPerStep()
Maximum number of edges created when a new node is added.
|
boolean |
nextEvents()
Step of the generator.
|
boolean |
produceExactlyMaxLinkPerStep()
True if the generator produce exactly
getMaxLinksPerStep() , else
it produce a random number of links ranging between 1 and
getMaxLinksPerStep() . |
void |
setExactlyMaxLinksPerStep(boolean on)
Set if the generator produce exactly
getMaxLinksPerStep()
(true), else it produce a random number of links ranging between 1 and
getMaxLinksPerStep() (false). |
void |
setMaxLinksPerStep(int max)
Set how many edge (maximum) to create for each new node added.
|
addEdge, addEdgeAttribute, addEdgeLabels, addNode, addNode, addNodeAttribute, addNodeLabels, clearKeptData, delEdge, delNode, isUsingInternalGraph, removeEdgeAttribute, removeNodeAttribute, setDirectedEdges, setEdgeAttributesRange, setNodeAttributesRange, setRandomSeed, setUseInternalGraph
addAttributeSink, addElementSink, addSink, attributeSinks, clearAttributeSinks, clearElementSinks, clearSinks, elementSinks, manageEvents, removeAttributeSink, removeElementSink, removeSink, sendAttributeChangedEvent, sendAttributeChangedEvent, sendEdgeAdded, sendEdgeAdded, sendEdgeAttributeAdded, sendEdgeAttributeAdded, sendEdgeAttributeChanged, sendEdgeAttributeChanged, sendEdgeAttributeRemoved, sendEdgeAttributeRemoved, sendEdgeRemoved, sendEdgeRemoved, sendGraphAttributeAdded, sendGraphAttributeAdded, sendGraphAttributeChanged, sendGraphAttributeChanged, sendGraphAttributeRemoved, sendGraphAttributeRemoved, sendGraphCleared, sendGraphCleared, sendNodeAdded, sendNodeAdded, sendNodeAttributeAdded, sendNodeAttributeAdded, sendNodeAttributeChanged, sendNodeAttributeChanged, sendNodeAttributeRemoved, sendNodeAttributeRemoved, sendNodeRemoved, sendNodeRemoved, sendStepBegins, sendStepBegins
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
addAttributeSink, addElementSink, addSink, clearAttributeSinks, clearElementSinks, clearSinks, removeAttributeSink, removeElementSink, removeSink
protected int maxLinksPerStep
protected boolean exactlyMaxLinksPerStep
maxLinksPerStep
.protected int sumDeg
protected int sumDegRemaining
public BarabasiAlbertGenerator()
public BarabasiAlbertGenerator(int maxLinksPerStep)
public BarabasiAlbertGenerator(int maxLinksPerStep, boolean exactlyMaxLinksPerStep)
public int getMaxLinksPerStep()
public boolean produceExactlyMaxLinkPerStep()
getMaxLinksPerStep()
, else
it produce a random number of links ranging between 1 and
getMaxLinksPerStep()
.getMaxLinksPerStep()
.public void setMaxLinksPerStep(int max)
max
- The new maximum, it must be strictly greater than zero.public void setExactlyMaxLinksPerStep(boolean on)
getMaxLinksPerStep()
(true), else it produce a random number of links ranging between 1 and
getMaxLinksPerStep()
(false).on
- Does the generator generates exactly
getMaxLinksPerStep()
.public void begin()
Generator.begin()
public boolean nextEvents()
setMaxLinksPerStep(int)
.
The complexity of this method is O(n) with n the number of nodes if the
number of edges created per new node is 1, else it is O(nm) with m the
number of edges generated per node.Generator.nextEvents()
protected void chooseAnotherNode()
public void end()
end
in interface Generator
end
in class BaseGenerator
Generator.end()
WebARTS Library Licensed Under the GNU - General Public License. Other Libraries licensed under their respective Open Source Licenses