Когда можно рассматривать подграф как гигантский компонент сети?

Question

Я делаю анализ устойчивости сети сети слов, встречающейся вместе.

Что я хотел бы понять, так это то, какова минимальная доля всех узлов, которые должны присутствовать в связанном компоненте (подграфе) сети, чтобы его можно было рассматривать как гигантский компонент.

Например, в сети из 20 000 узлов, если максимальное число узлов, которое содержит подграф, скажем 3, можно ли считать его гигантским компонентом?

Answer 1

Как я понимаю, вы спрашиваете об определении термина "гигантский компонент".

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

Это качественное наблюдение. Нет точного определения «гигантского компонента» на основе доли принадлежащих ему узлов. Только наблюдение, что в случайном графе множества узлов есть пороговая связность, вокруг которой доля узлов, принадлежащих к наибольшему компоненту, очень резко возрастет.

Есть ли проблема, которую вы пытаетесь решить или понять, или вы просто спрашиваете об определении этого термина?