Редкая сеть - Sparse network

В сетевая наука, а разреженная сеть имеет намного меньше ссылок, чем возможное максимальное количество ссылок в этой сети (обратное плотная сеть). Изучение разреженных сетей - относительно новая область, в первую очередь стимулированная изучением реальных сетей, таких как социальные и компьютерные сети.^[1]

Описание

Количество ссылок варьируется от сети к сети. Количество ссылок в сети может быть больше, чем количество узлов в сети. Если каждый узел связан со всеми другими узлами, кроме самого себя (сеть не обязательно должна содержать петли), тогда этот тип сети называется полный и разве это не редкость: L = ссылки; N = узлы

L является полным (а не разреженным), если ${\displaystyle L=L_{max}}$ за ${\displaystyle L_{max}=N(N-1)/2}$

Если количество ссылок намного меньше максимального количества ссылок, то это разреженная сеть^[1]. В сетях, в которых сложно связать узлы, можно обнаружить разреженные возможности подключения:

L, если разреженный iff ${\displaystyle L<<L_{max}}$ за ${\displaystyle L_{max}=N(N-1)/2}$

Большинство реальных сетей разрежены, однако их все еще можно эффективно проанализировать. Обычно в реальных сетях есть безмасштабный (степенное) распределение узловых степеней, что означает, что в одной сети есть несколько чрезвычайно связанных узлов и много редко связанных узлов.^{[2][сомнительный ]}

Распределение степени узла

Распределение степени узла изменяется с увеличением возможности подключения. Как предполагает Flickr Network Analysis, разная плотность ссылок в сложных сетях имеет разное распределение узлов.^[3] Редко связанные сети имеют безмасштабное распределение по степенному закону. По мере увеличения возможности подключения сети демонстрируют все большее отклонение от степенного закона. Одним из основных факторов, влияющих на возможность подключения к сети, является сходство узлов. Например, в социальные сети, люди, вероятно, будут связаны друг с другом, если они имеют общее социальное происхождение, интересы, вкусы, убеждения и т. д. В контексте биологических сетей белки или другие молекулы связаны между собой, если они имеют точное или дополнительное соответствие своей сложной поверхности.^[4]

Общая терминология

Если узлы в сетях не взвешены, структурные компоненты сети могут быть показаны через матрица смежности. Если большинство элементов в матрице равны нулю, такая матрица называется разреженная матрица. Напротив, если большинство элементов отличны от нуля, то матрица плотный. Разреженность или плотность матрицы определяется долей нулевого элемента к общему количеству элементов в матрице. Точно так же в контексте теория графов, если количество ссылок близко к максимальному, то граф будет известен как плотный граф. Если количество ссылок меньше максимального количества ссылок, этот тип графиков называется разреженный граф.^[5]

Приложения

Sparse Network можно найти в Социальное, компьютер и биологические сети, а также его приложения можно найти в транспорт, линии электропередач, сети цитирования и т. д. Поскольку большинство реальных сетей являются большими и разреженными, было разработано несколько моделей для их понимания и анализа.^[6] Эти сети вдохновили немногочисленные сеть на кристалле дизайн в многопроцессорном встроенном компьютерная инженерия.

Рекомендации

1. Барабаши, Альберт-Ласло (2015). Сетевые науки. Издательство Кембриджского университета. Получено 25 мая 2015.
2. Шольц, Матиас. «Подключение - общество с высокими связями». Сетевые науки. Получено 25 мая 2015.
3. http://jdmdh.episciences.org/77/pdf
4. Шольц, Матиас (7 января 2015 г.). «Сходство узлов как основной принцип подключения в сложных сетях». Журнал интеллектуального анализа данных и цифровых гуманитарных наук (77). Получено 25 мая 2015.
5. Никамп, Дуэйн К. «Введение в сети». Math Insight. Получено 25 мая 2015.
6. Грибонваль, Реми. «Разреженные модели, алгоритмы и обучение для крупномасштабных данных». МАЛЕНЬКИЙ. Получено 25 мая 2015.