Просмотр исходного текста страницы Смежность сети

'''Смежность'''- характеристика социальной сети, описывающая связь вершин в одну цепь.

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

Понятие смежности имеет для сети фундаментальное значение. Высокая смежность сети предполагает, что такая сеть надежна.

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

Литература:

Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с