Разреженная сеть

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

Идея гораздо меньшего количества ссылок, конечно, разговорная и неформальная. Хотя порог для конкретной сети может быть изобретен, не существует универсального порога, который бы определял, что на самом деле означает гораздо меньше . В результате не существует формального ощущения разреженности какой-либо конечной сети, несмотря на широко распространенное мнение, что большинство эмпирических сетей действительно разрежены. Однако в случае моделей бесконечных сетей существует формальное ощущение разреженности, определяемое поведением количества ребер (M) и/или средней степени ( ⟨k⟩ ) по мере увеличения количества узлов (N). до бесконечности.

Определения

Простая невзвешенная сеть размером $N$ называется разреженным, если число связей $M$ в нем гораздо меньше максимально возможного количества ссылок $M_{max}$:

$M\ll M_{max}={N \choose 2}$ .

В любой данной (реальной) сети количество узлов N и связей M представляет собой всего лишь два числа, поэтому значение гораздо меньшего знака ( $\ll$ выше) является чисто разговорным и неформальным, как и утверждения типа «многие реальные сети редки».

Однако если мы имеем дело с синтетической последовательностью графов $G_{N}$или сетевая модель, которая четко определена для сетей $G_{N}$ любого размера N = 1,2,..., $\infty$, тогда $\ll$ приобретает свой обычный формальный смысл:

$M\ll M_{max}\iff M=o(M_{max})\iff \lim _{N\rightarrow \infty }{\frac {M}{M_{max}}}=0$.

Другими словами, сетевая последовательность или модель $G_{N}$ называется плотным или разреженным в зависимости от того, соответствует ли (ожидаемая) средняя степень $\langle k\rangle =2M/N$ в $G_{N}$ масштабируется линейно или сублинейно с помощью N :

$G_{N}$ является плотным, если $\langle k\rangle =O(N)$;

$G_{N}$ является разреженным, если $\langle k\rangle =o(N)$.

Важным подклассом разреженных сетей являются сети, средняя степень которых либо постоянна, либо сходится к константе. Некоторые авторы называют только такие сети разреженными, другие оставляют за ними специальные названия:

$G_{N}$ является действительно разреженным , чрезвычайно разреженным или ультраразреженным, если $\langle k\rangle =O(1)$.

Также существуют альтернативные, более строгие определения разреженности сети, требующие сходимости распределения степеней в $G_{N}$ до четко определенного предела при $N\rightarrow \infty$. Согласно этому определению, граф N-звезды $S_{N}$, например, не является редким.

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

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

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

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

Приложения

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

Разреженные сети также удешевляют вычисления, позволяя хранить сеть в виде списка смежности , а не матрицы смежности . Например, при использовании списка смежности перебор соседей узла может быть достигнут за O(M/N), тогда как при использовании матрицы смежности это достигается за O(N).