Социальные графы можно определить через набор вершин-людей с некоторыми свойствами и методами, которыми они воздействуют через имеющиеся связи-ребра на другие вершины. Ребра нагружены некоторой ценой для установления связи инцидентных ему вершин. Некоторые психические усилия, сумма денег и т.п. В зависимости от состояния этого ребра возможно применение методов начала ребра на его конец (беседа, секс, занять денег). Граф нестационарен: меняются веса вершин (социальная значимость), слабеют или усиливаются новые связи. Появляются новые вершины (рождение детей), с течением времени наследующие связи от предков.
Вычислительная сложность обсчета такой системы пропорциональна количеству ребер (в полном графе из n вершин это n*(n-1)/2). Но в исходном графе могут быть выделены некоторые подграфы в соответствии с правом крови, профессиональными интересами, национальной принадлежностью и прочими признаками. В этом случае, группа вершин может рассматриваться как одна (эффект кластеризации). Мастерство великого правителя и составляет искусство кластеризации точек, ведь связь точки и кластера точек вычислительно более проста. Заметим, что подобным образом кластеризуются клетки организмов, преобразуясь к макропростым объектам (лист дерева).
Рассмотренная в первом абзаце структура полного социального графа линейная, одноуровневая. Однако если обратиться к примерам животного мира, то тут характерно выстраивание иерархий (прайды, стаи, табуны). Этот естественный природный процесс копирует на свой лад и человек. Причина, на наш математический взгляд, та же: уменьшение вычислительной сложности модели. Так, если у одного начальника семь подчиненных, то количество связей равно семи. Если бы эта структура была полным графом (все восемь человек были равноправны), то число связей было бы равно 8*7/2=28.

via субботний моцион с Гаггей Гагеевичем