Список использованных источников

• 1. Граф (математика) // ru.wikipedia.org: Википедия — свободная энциклопедия. URL: http://ru.wikipedia.org/wiki/Граф_(математика) (дата обращения 26.05.2013)
• 2. Albert R., Barabasi A. Statistical mechanics of complex networks // Rev. Mod. Phys. 2002. V. 74 P. 47−97
• 3. Олемской А. И. Статистика сложных сетей (обзор) / А. И. Олемской, И. А. Олемской // «Вiсник СумДУ». — 2006. — № 6 (90). — С.21−47
• 4. Автоматическая обработка текстов на естественном языке и компьютерная лингвистика: учебн. пособие / Большакова Е. И., Клышинский Э. С., Ландэ Д. В., Носков А. А., Пескова О. В., Ягунова Е. В. — М.: МИЭМ, 2011. — 272 с.
• 5. Т. А. Леванова, М. А. Комаров, Е. Ю. Кадина, Г. В. Осипов Структуры последовательной активности в нейронных сетях со случайными связями // Вестник Нижегородского университета им. Н. И. Лобачевского. — 2010. — № 2 (1). — С. 131−139
• 6. Задорожный В. Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления. — 2010. — № 6. — С. 2−11.
• 7. Юдин Е. Б. Генерация случайных графов предпочтительного связывания // Омский научный вестник. — 2010. — № 2 (90). — С. 7−13.
• 8. Задорожный, В.Н., Юдин, Е. Б. Структурные свойства безмасштабного графа Барабаши-Альберт // Автоматика и телемеханика. — 2012. — № 4. — С. 131−150.
• 9. Задорожный, В.Н., Юдин, Е. Б. Точная теория графа Барабаши-Альберт // Омский научный вестник. — 2009. — № 3 (83). — С.13−19
• 10. Юдин Е. Б. Методы структурной идентификации стохастических сетей и генерации случайных графов в задачах моделирования сложных систем: Дис. на соискание учёной степени канд. техн. наук. — Омск., 2012. — С. 47−65
• 11. Данные о сетях [Электронный ресурс]. — Режим доступа: http://vlado.fmf.uni-lj.si/pub/networks/data/, свободный. — Загл. с экрана. — Яз. англ.
• 12. Структура сети маршрутизаторов Интернет (2006 г.). URL: http://www.cise.ufl.edu/ research/sparse/mat/Pajek/internet.mat (дата обращения: 01.09.2009).
• 13. Структура сети участия актёров в общих фильмах. URL: http://www.nd.edu/~networks/resources/actor/actor.dat.gz (дата обращения: 03.02.2010).
• 14. Задорожный В. Н., Юдин Е. Б., Овчинникова Е. В., Ганеева М. И. Сравнение случайных графов с моделями сетей по диаметру // материалы IV регион. науч.-практ. конф (Омск, 2012). — ОмГТУ; 2012. — С. 100−101
• 15. Задорожный В. Н., Бояршинов К. Н. Структурные характеристики графов: коэффициенты кластеризации // материалы IV регион. науч.-практ. конф (Омск, 2012). — ОмГТУ; 2012. — С. 91−93
• 16. Юдин Е. Б., Ганеева М. И. Расчёт коэффициента кластеризации для присоединения в графай предпочтительного связывания // материалы V Всерос. науч.-практ. конф. студентов, аспирантов, работников образования и пром-сти (Омск, 23−26 апр. 2013 г.). — ОмГТУ; 2013. — С. 92−95
• 17. Юдин Е. Б., Овчинникова Е. В. О выборе вершины для присоединения в графах предпочтительного связывания // материалы V Всерос. науч.-практ. конф. студентов, аспирантов, работников образования и пром-сти (Омск, 23−26 апр. 2013 г.). — ОмГТУ; 2013. — С. 95−97
• 18. Сеть автономных систем Интернет, воссозданная на основе BGP таблиц URL: http://www-personal.umich.edu/~mejn/netdata/as-22july06.zip (дата обращения: 01.09.2009).

Приложение А.

(обязательное) Листинг алгоритма с гарантированным появлением хотя бы одного треугольника при присоединении новой вершины.

import edu.uci.ics.jung.algorithms.generators.random.BarabasiAlbertGenerator;

import edu.uci.ics.jung.graph.DirectedSparseMultigraph;

import edu.uci.ics.jung.graph.Graph;

import edu.uci.ics.jung.graph.UndirectedSparseMultigraph;

import edu.uci.ics.jung.graph.util.EdgeType;

import edu.uci.ics.jung.graph.util.Pair;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Random;

import java.util.Set;

public class m6_PowerOrtGenerator {.

Para temp = new Para (0, 0);

Mapnew HashMap ();

Mapnew HashMap ();

int initN = 4;// addEd1 = 3;

Graph graph;

protected PrefferentialAttachment attachRule;

protected Factory vertexFactory;

protected Factory edgeFactory;

protected double numEdgesToAttach[];

public m6_PowerOrtGenerator (Factory vertexFactory,.

Factory edgeFactory, double[] probEdgesToAttach, PrefferentialAttachment attachRule).

{.

double s=0.;

for (double d: probEdgesToAttach).

{.

s=s+d;

}.

assert Math.abs(s-1.)<0.1 :" Сумма вероятностей по различным значениям «.

+ «числа добавляемых на шаге ребер должна равняться 1» ;

this.vertexFactory = vertexFactory;

this.edgeFactory = edgeFactory;

this.numEdgesToAttach= probEdgesToAttach;

this.attachRule =attachRule;

mRand = new Random ();

}.

public Graph evolve (int step){//, int m, double lyamda, Graph graph).

graph = new UndirectedSparseMultigraph ();

int m =3;

initN = m + 1;

// инициализация полносвязного графа и добавление в слои.

mapLayers.put (m, new LinkedList ());

for (int i = 0; i < initN; i++) {.

V n = vertexFactory. create ();

graph.addVertex (n);

List list = mapLayers. get (m);

list.add (n);

}.

Object[] mass = graph. getVertices ().toArray ();

for (int i = 0; i < mass. length — 1; i++).

for (int j = i + 1; j < mass. length; j++) {.

E link = edgeFactory. create ();

graph.addEdge (link, (V) mass[i], (V) mass[j],.

EdgeType.UNDIRECTED);

}.

//поместить все рёбра в матрицу рёбер

for (E l0: graph. getEdges ()).

{.

Pair pa = graph. getEndpoints (l0);

int min = graph. degree (pa.getFirst ());

int max = graph. degree (pa.getSecond ());

Para temp = null;

add2pair (max, min, l0);

}.

// Обращаемся к матрице. Находим одно из рёбер и, тем самым,.

// находим два требуемых узла. Остальные берём случайно.

for (int i = 0; i < step; i++).

{.

// разыгрываем две случайные величины, определяющие номера слоёв.

int addEd= getNumAttachToAttach ();

if(addEd==0)System.out.println («нельзя вершин без узлов»);

// массив выбранных индексов.

int[] indexes = new int[addEd];

Set setLink = new HashSet ();

List listNodes = new LinkedList ();

Mapnew HashMap ();

formConPairVert (indexes, mapPairs);

Pair pair= mapPairs. keySet ().iterator ().next ();

// получаем список узлов для присоединения.

listNodes.add (pair.getFirst ());

if(indexes.length>1)listNodes.add (pair.getSecond ());

for (int j = 0; j < indexes. length; j++).

{.

//из тех, чьи индексы не вошли в Map.

Iterator.

boolean isUse= false;

while (it.hasNext ()){.

Pair pairK= it. next ();

int k1=pairK.getFirst (), k2=pairK.getSecond ();

if (j ==k1||j ==k2)isUse = true;

}.

if(!isUse).

listNodes.add (mapLayers.get (indexes[j]).get (.

mRand.nextInt (mapLayers.get (indexes[j]).size ())));

}.

// формируем список рёбер, которых затронут изменения.

for (Iterator iterator = listNodes. iterator (); iterator. hasNext ();).

{.

V myNode = (V) iterator. next ();

Collection list_j = graph. getIncidentEdges (myNode);

for (Iterator it = list_j.iterator (); it. hasNext ();) {.

E link = it. next ();

setLink.add (link);

}.

}.

// удаляем из списка вершин, те, чьи степени изменятся.

for (Iterator iterator = listNodes. iterator (); iterator. hasNext ();).

{.

V myNode = (V) iterator. next ();

mapLayers.get (graph.degree (myNode)).remove (myNode);

}.

// удаляем из списка рёбер такие, которых затронули изменения.

for (E l0: setLink).

{.

Pair pa = graph. getEndpoints (l0);

int min = graph. degree (pa.getFirst ());

int max = graph. degree (pa.getSecond ());

Para temp = null;

if (min > max).

temp = new Para (max, min);

else.

temp = new Para (min, max);

pair_matrix.get (temp).remove (l0);

}.

V new_n = vertexFactory. create ();

// добавляем ребро в граф.

Map newEdges = new HashMap ();

for (Iterator iterator = listNodes. iterator (); iterator. hasNext ();).

{.

V myNode = (V) iterator. next ();

E l1 = edgeFactory. create ();

newEdges.put (l1, myNode);

graph.addEdge (l1, new_n, myNode);

}.

// переносим в соответв слой новую вершину и все изменённые вершины.

listNodes.add (new_n); // добавляем к числу удалённых вершин новую и заносим всё в слои.

for (Iterator iterator = listNodes. iterator (); iterator. hasNext ();).

{.

V myNode = (V) iterator. next ();

addToLayer (myNode, graph. degree (myNode));

}.

// Добавляем новые рёбра в матрицу рёбер

for (E li: newEdges. keySet ()) {.

int min = addEd;

int max = graph. degree (newEdges.get (li));

add2pair (min, max, li);

}.

//Добавляем изменённые рёбра в матрицу рёбер

for (E l0: setLink) {.

Pair pa = graph. getEndpoints (l0);

int min = graph. degree (pa.getFirst ());

int max = graph. degree (pa.getSecond ());

add2pair (min, max, l0);

}.

}.

return graph;

}.

private void formConPairVert (int[] indexes, Map.

int k1 = 0, k2 = 0;

V n1 = null, n2 = null;

E p = null;

do {.

for (int j = 0; j < indexes. length; j++) {.

indexes[j] = getK ();

}.

Arrays.sort(indexes);

// на основе индексов обращаемся к матрице и формируем список.

// рёбер для выбора.

List listLink_ = new LinkedList ();

for (int j = 0; j < indexes. length — 1; j++) {.

for (int k = j + 1; k < indexes. length; k++) {.

Para pr = new Para (indexes[j], indexes[k]);

if (pair_matrix.get (pr) ≠ null.

&& pair_matrix.get (pr).size () > 0).

listLink_.addAll (pair_matrix.get (pr));

}.

}.

n1 = null;

n2 = null;

if ((listLink_.size () > 0)) {.

p = listLink_.get (mRand.nextInt (listLink_.size ()));

if (p == null).

System.out.println («ff»);

Pair par = graph. getEndpoints (p);

int i1 = graph. degree (par.getFirst ());

int i2 = graph. degree (par.getSecond ());

boolean b1 = true, b2 = true;

for (int j = 0; j < indexes. length; j++) {.

if (indexes[j] == i1 && b1) {.

k1 = j;

b1 = false;

continue;

}.

if (indexes[j] == i2 && b2) {.

k2 = j;

b2 = false;

continue;

}.

}.

} else {.

int i1 = mRand. nextInt (indexes.length);

int i2 = i1;

do.

i2 = mRand. nextInt (indexes.length);

while (i2 == i1&&(indexes.length>1));//пока они равны и длина >1.

k1 = i1;

k2 = i2;

n1 = mapLayers. get (indexes[i1]).get (.

mRand.nextInt (mapLayers.get (indexes[i1]).size ()));

n2 = mapLayers. get (indexes[i2]).get (.

mRand.nextInt (mapLayers.get (indexes[i2]).size ()));

}.

listLink_.clear ();

} while ((p == null) && (n1 == n2));

Pair pair1;

if (p ≠ null) {.

pair1 = graph. getEndpoints (p);

} else

pair1 = new Pair (n1, n2);

Pair pair2 =new Pair (k1, k2);

map.put (pair1, pair2);

}.

private int getNumAttachToAttach () {.

double s=0.;

double r1=mRand.nextDouble ();

int addEd =0;

for (int j = 0; j < numEdgesToAttach. length; j++) {.

s=s+numEdgesToAttach[j];

if(s>r1).

{.

addEd = j;

break;

}.

}.

return addEd;

}.

private void add2pair (int min, int max, E link) {.

if (min > max).

{.

int temp= max;

max=min;

min=temp;

}.

Para para = new Para (min, max);

List p = pair_matrix.get (para);

if (p == null) {.

p = new ArrayList ();

pair_matrix.put (para, p);

}.

p.add (link);

}.

Random mRand = new Random ();

double f (int k) {.

return attachRule. f (k);

}.

private int getK () {.

// разыгрываем.

int k = 0;

double rand = mRand. nextDouble ();

double tr = 0;

// считаем знаменатель.

double sum = 0.0;

for (int op: mapLayers. keySet ()).

sum = sum + f (op) * mapLayers. get (op).size ();

double sum2 = 0.0;

for (int l: mapLayers. keySet ()) {.

int A = mapLayers. get (l).size ();

tr = tr + ((double) A * f (l)) / sum;

if (rand < tr) {.

k = l;

break;

}.

}.

return k;

}.

private void addToLayer (V n, int i) {.

List list = mapLayers. get (i);

if (list == null) {.

list = new LinkedList ();

mapLayers.put (i, list);

}.

if (!list.contains (n)).

list.add (n);

}.

}.

Листинг алгоритма с разбиением вершин для присоединения на пары, из которых производится поиск двух связных вершин (что обеспечивает образование треугольника при присоединении).

import edu.uci.ics.jung.algorithms.generators.random.BarabasiAlbertGenerator;

import edu.uci.ics.jung.graph.DirectedSparseMultigraph;

import edu.uci.ics.jung.graph.Graph;

import edu.uci.ics.jung.graph.UndirectedSparseMultigraph;

import edu.uci.ics.jung.graph.util.EdgeType;

import edu.uci.ics.jung.graph.util.Pair;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Random;

import java.util.Set;

public class m7_PowerOrtGenerator {.

Para temp = new Para (0, 0);

Mapnew HashMap ();

Mapnew HashMap ();

int initN = 4;// addEd1 = 3;

Graph graph;

protected PrefferentialAttachment attachRule;

protected Factory vertexFactory;

protected Factory edgeFactory;

protected double numEdgesToAttach[];

int maxlayer=0;

public m7_PowerOrtGenerator (Factory vertexFactory,.

Factory edgeFactory, double[] probEdgesToAttach, PrefferentialAttachment attachRule).

{.

double s=0.;

for (double d: probEdgesToAttach).

{.

s=s+d;

}.

assert Math.abs(s-1.)<0.1: «Сумма вероятностей по различным значениям «.

+ «числа добавляемых на шаге ребер должна равняться 1» ;

this.vertexFactory = vertexFactory;

this.edgeFactory = edgeFactory;

this.numEdgesToAttach= probEdgesToAttach;

this.attachRule =attachRule;

mRand = new Random ();

}.

public Graph evolve (int step){//, int m, double lyamda, Graph graph).

maxlayer=0;

graph = new UndirectedSparseMultigraph ();

int m =3;

initN = m + 1;

// Инициализация полносвязного графа. Добавление в слои.

mapLayers.put (m, new LinkedList ());

for (int i = 0; i < initN; i++) {.

V n = vertexFactory. create ();

graph.addVertex (n);

List list = mapLayers. get (m);

list.add (n);

}.

Object[] mass = graph. getVertices ().toArray ();

for (int i = 0; i < mass. length — 1; i++).

for (int j = i + 1; j < mass. length; j++) {.

E link = edgeFactory. create ();

graph.addEdge (link, (V) mass[i], (V) mass[j],.

EdgeType.UNDIRECTED);

}.

//Помещаем все рёбра в матрицу рёбер

for (E l0: graph. getEdges ()) {.

Pair pa = graph. getEndpoints (l0);

int min = graph. degree (pa.getFirst ());

int max = graph. degree (pa.getSecond ());

Para temp = null;

add2pair (max, min, l0);

}.

// Обращаемся к матрице. Находим одно из рёбер и, тем самым,.

// находим два требуемых узла. Остальные берём случайно.

for (int i = 0; i < step; i++) {.

// разыгрываем две случайные величины, определяющие номера слоёв.

int addEd= getNumAttachToAttach ();

if(addEd==0)System.out.println («нельзя вершин без узлов»);

// массив выбранных индексов.

int[] indexes = new int[addEd];

Set setLink = new HashSet ();

List listNodes = new LinkedList ();

Map mapPairs = new HashMap ();

for (int j = 0; j < indexes. length; j++) {.

indexes[j] = getK ();

if(indexes[j]>maxlayer)maxlayer =indexes[j];

}.

formConPairVert (indexes, listNodes);

// формируем список рёбер, которых затронут изменения.

for (Iterator iterator = listNodes. iterator (); iterator. hasNext ();) {.

V myNode = (V) iterator. next ();

Collection list_j = graph. getIncidentEdges (myNode);

for (Iterator it = list_j.iterator (); it. hasNext ();) {.

E link = it. next ();

setLink.add (link);

}.

}.

// удаляем из списка вершины, те, чьи степени изменятся.

for (Iterator iterator = listNodes. iterator (); iterator. hasNext ();) {.

V myNode = (V) iterator. next ();

mapLayers.get (graph.degree (myNode)).remove (myNode);

} // удаляем из списка рёбер такие, которые затронули изменения.

for (E l0: setLink) {.

Pair pa = graph. getEndpoints (l0);

int min = graph. degree (pa.getFirst ());

int max = graph. degree (pa.getSecond ());

Para temp = null;

if (min > max).

temp = new Para (max, min);

else.

temp = new Para (min, max);

pair_matrix.get (temp).remove (l0);

}.

V new_n = vertexFactory. create ();

// добавляем рёбра в граф.

Map newEdges = new HashMap ();

for (Iterator iterator = listNodes. iterator (); iterator. hasNext ();) {.

V myNode = (V) iterator. next ();

E l1 = edgeFactory. create ();

newEdges.put (l1, myNode);

graph.addEdge (l1, new_n, myNode);

}.

// переносим в соответствующий слой новую вершину и все изменённые вершины.

listNodes.add (new_n); // добавляем к числу удаленных вершин новую и заносим всё в слои.

for (Iterator iterator = listNodes. iterator (); iterator. hasNext ();) {.

V myNode = (V) iterator. next ();

addToLayer (myNode, graph. degree (myNode));

}.

// Добавляем новые рёбра в матрицу рёбер

for (E li: newEdges. keySet ()) {.

int min = addEd;

int max = graph. degree (newEdges.get (li));

add2pair (min, max, li);

}.

//Добавляем изменённые рёбра в матрицу рёбер

for (E l0: setLink) {.

Pair pa = graph. getEndpoints (l0);

int min = graph. degree (pa.getFirst ());

int max = graph. degree (pa.getSecond ());

add2pair (min, max, l0);

}.

}.

System.out.println («^^» +count);

return graph;

} int count=0;

private void formConPairVert (int[] m, List listNodes) {.

int k1, k2;

Set set = new HashSet ();

if(m.length>1){.

for (int i = 0; i < m. length/2; i++) {.

if(m[i]>m[m.length/2+i]) {k1 = m[ m. length/2+i]; k2= m[i]; }.

else {k1 = m[i]; k2= m[ m. length/2+i]; }.

Para pr = new Para (k1, k2);

List list =pair_matrix.get (pr);

E edge = null;

if(list≠null){.

count++;

for (E e: list) {.

if(!set.contains (e)).

edge = e;

set.add (edge);

break;

}.

}.

if (edge ≠ null) {.

Pair pair2= graph. getEndpoints (edge);

listNodes.add (pair2.getFirst ());

listNodes.add (pair2.getSecond ());

} else

{.

V n1 = mapLayers. get (k1).get (.

mRand.nextInt (mapLayers.get (k1).size ()));

V n2 = mapLayers. get (k2).get (.

mRand.nextInt (mapLayers.get (k2).size ()));

listNodes.add (n1);

listNodes.add (n2);

}.

}.

// если есть нечётное ребро.

if(m.length%2==1).

listNodes.add (mapLayers.get (m[m.length-1]).get (mRand.nextInt (mapLayers.get (m[m.length-1]).size ())));

}.

//если ребро одно.

else {.

listNodes.add (mapLayers.get (m[0]).get (.

mRand.nextInt (mapLayers.get (m[0]).size ())));

}.

}.

private int getNumAttachToAttach () {.

double s=0.;

double r1=mRand.nextDouble ();

int addEd =0;

for (int j = 0; j < numEdgesToAttach. length; j++) {.

s=s+numEdgesToAttach[j];

if(s>r1).

{.

addEd = j;

break;

}.

}.

return addEd;

}.

private void add2pair (int min, int max, E link) {.

if (min > max).

{.

int temp= max;

max=min;

min=temp;

}.

Para para = new Para (min, max);

List p = pair_matrix.get (para);

if (p == null) {.

p = new ArrayList ();

pair_matrix.put (para, p);

}.

p.add (link);

}.

Random mRand = new Random ();

double f (int k) {.

return attachRule. f (k);

}.

private int getK () {.

// разыгрываем.

int k = 0;

double rand = mRand. nextDouble ();

double tr = 0;

// считаем знаменатель.

double sum = 0.0;

for (int op: mapLayers. keySet ()).

sum = sum + f (op) * mapLayers. get (op).size ();

double sum2 = 0.0;

for (int l: mapLayers. keySet ()) {.

int A = mapLayers. get (l).size ();

tr = tr + ((double) A * f (l)) / sum;

if (rand < tr) {.

k = l;

break;

}.

}.

return k;

}.

private void addToLayer (V n, int i) {.

List list = mapLayers. get (i);

if (list == null) {.

list = new LinkedList ();

mapLayers.put (i, list);

}.

if (!list.contains (n)).

list.add (n);

}.

}.