Быстрые и точные эвристики для оценки bus-factor

Граф представляет собой пару $\mathcal{G}=(V,E)$, где $V$ — множество вершин, а $E\subseteq V\times V$ — множество ребер. Граф представляется через свою матрицу смежности $A$; причем $A_{ij}=1$, если вершины $i$ и $j$ соединены, и $A_{ij}=0$ в противном случае. Степень $k_{i}$ вершины $i$ — это количество соединенных с ней вершин, то есть $k_{i}=\sum_{j}A_{ij}$. Подграф графа $G$ представляет собой граф, индуцированный подмножеством $S\subseteq V$ вершин графа $G$, и обозначается как $G[S]$. Компонента связности графа — это связанный подграф, который не является частью никакого другого связанного подграфа.

Если множество вершин $V$ может быть разделено на два множества $V_{1}$ и $V_{2}$ с $V_{1}\cap V_{2}=\emptyset$ и $V_{1}\cup V_{2}=V$, таких что $\forall(i,j)\in E\;i\in V_{1}\wedge j\in V_{2}$, то граф называется двудольным. Двудольный граф является подходящим инструментом для представления связей между множеством людей и множеством артефактов, таких как файлы исходного кода, документы, модули, задачи и так далее. Без потери общности, в данной статье мы ссылаемся на двудольные графы людей и задач, которые мы обозначаем как $\mathcal{G}=(P,T,E)$, где $P$ — это множество людей, $T$ — множество задач, а $E$ — множество ребер между людьми и задачами. Мы говорим, что человек $i$ покрывает задачу $j$, если $(i,j)\in E$, и мы говорим, что задача $j$ покрыта, если с ней связан по крайней мере один человек; то есть если $k_{j}>0$. Мы ссылаемся на задачи в компоненте связности как на связанные задачи и ссылаемся на наибольшее количество задач в компоненте связности как на максимальное количество связанных задач, обозначая его как $\tau(G)$. Наконец, $k_{P}=\max_{i\in P}\sum_{i}A_{ij}$ и $k_{T}=\max_{j\in T}\sum_{j}A_{ij}$ обозначают соответственно наибольшую степень среди людей и наибольшую степень среди задач.

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

Удобный способ генерации графов с сильно асимметричными распределениями степеней заключается в выборке степеней узлов из степенного распределения, соединяя узлы случайным образом в соответствии с выбранным распределением степеней. Степенное распределение определяется следующей функцией плотности вероятности:

где $0<\lambda<1$ представляет собой параметр, регулирующий асимметрию распределения: чем выше $\lambda$, тем менее асимметрично распределение (при $\lambda=1$ мы получаем равномерное распределение); $k_{\min}$ и $k_{\max}$ регулируют носителем $f$, который равен $[k_{\min},k_{\min}+k_{\max}]$, и, следовательно, максимальную и минимальную степень в графе степенного закона.

Алгоритм 1 предоставляет процедуру для создания двудольного графа с распределением степеней, подчиняющимся степенному закону. Он работает следующим образом: сначала он выбирает два распределения степеней со степенным законом без изолированных узлов (ни у одного узла нет степени 0). Затем он гарантирует, что эти два распределения степеней имеют одинаковую сумму, и генерирует граф, соединяя случайные узлы в соответствии с заданными степенями и без создания двойных рёбер между одной и той же парой узлов. Наконец, если граф не является связным, выполняется процедура случайного переподключения рёбер, которая не изменяет распределения степеней..

Наиболее распространенная мера bus-factor происходит от Авелино и др., которые предположили, что проект останавливается, если количество покрытых задач меньше $t\times m$, где $0<t<1$ является входным параметром. Пусть $\mathrm{cov}(G)=|\{j:k_{j}>0,\forall j\in T\}|$ — это количество покрытых задач в $G$, тогда bus-factor согласно Авелино и др. выглядит следующим образом:

Другими словами, $A(G)$ представляет собой размер наименьшего подмножества людей $S$, удаление которого из $G$ приводит к тому, что более чем $t\times m$ задач оказываются изолированными. Авелино и др. предлагают установить $t=0.5$.

Связанная мера bus-factor, которая использовалась в прошлом до внедрения (2), предложена Зазворкой и др. и определяется следующим образом:

то есть наибольшее подмножество $S$ людей такое, что при удалении из $G$ минимальное количество покрытых задач больше или равно $t\times m$.

Данная лемма подразумевает, что решение для (2) также является решением для (3). Однако решение (2) является NP-трудным; поэтому на практике мы используем аппроксимирующий алгоритм для его оценки. Эвристика, предложенная Авелино и соавторами, заключается в удалении людей в порядке убывания их степени до тех пор, пока количество покрытых задач не станет меньше 50%. Количество людей, удаленных таким образом, является оценкой bus-factor..

Недавно Пикколо и соавторы предложили новую метрику bus-factor, которая является нормализованной и не зависит от входного порогового значения (Piccolo et al., 2024; Piccolo et al., 2025). Они утверждают, что использование порогового значения является в некоторой степени произвольным и что покрытие задач не отражает степень фрагментации знаний в проекте по мере ухода людей. Например, проект, состоящий из $n$ несвязных диад (то есть ребра, соединяющего одного человека с одной задачей), имеет все покрытые задачи, но Пикколо и соавторы (Piccolo et al., 2025) утверждают, что он обладает высокой степенью фрагментации и что это должно учитываться метрикой bus-factor..

Следовательно, они заменили покрытие максимальным количеством связанных задач; то есть наибольшим числом задач, содержащихся в связанном компоненте. Чтобы не зависеть от порогового значения, они предложили вычислять площадь под кривой затухания максимального числа связанных задач по мере удаления людей, нормируя ее на теоретический максимум (полученный для соответствующего полносвязного двудольного графа). Поэтому они определяют bus-factor как минимальную площадь под кривой по всем возможным порядкам удаления людей (Piccolo et al., 2024; Piccolo et al., 2025).

Формально, пусть $\pi:P\rightarrow P$ будет перестановкой людей в $P$, $\Pi(P)$ будет пространством всех перестановок $P$, а $G_{i}^{\pi}=G[P\setminus\{\pi_{1},\pi_{2},\dots,\pi_{i}\}]$ будет остаточным графом, полученным путем удаления всех людей вплоть до i-го человека в перестановке $\pi$. Напомним, что $\tau(G)$ — это максимальное количество задач, соединенных в компонент $G$. Фактор автобуса согласно Piccolo et al. (Piccolo et al., 2025) определяется следующим образом:

where $G_{0}^{\pi}=G$. Note that the term $\sum_{i=1}^{n}\tau(G_{i-1}^{\pi})+\tau(G_{i}^{\pi})$ in (4) is just the standard trapezoid rule for computing the area under the curve and the denominator ${2n-1}$ is the maximum theoretical value, obtained for a fully connected graph with $n$ people. As such, $\mathcal{P}(G)$ takes values in $[0,1]$.

Piccolo и др. (Piccolo et al., 2025) доказали, что решение (4) является NP-сложным, и поэтому они предлагают аппроксимировать его путем упорядочивания людей в $\pi$ в порядке убывания степени.

Мы начинаем с пустого упорядочивания $\pi$. На каждом шаге для каждого человека $p\in P\setminus\pi$ мы определяем его текущее покрытие как количество задач, которые он покрывает и которые еще не покрыты людьми в $\pi$. Человек с наименьшим текущим покрытием добавляется в конец $\pi$. Этот процесс продолжается до тех пор, пока все люди не будут добавлены в упорядочивание $\pi$⟧.

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

Наивная реализация минимального покрытия потребовала бы пересчета эффективного покрытия задач для каждого человека, связанного хотя бы с одной задачей, покрытой последним человеком, добавленным в $\pi$. Обновление эффективного покрытия затронутых людей требует $O(|E|)$ операций. Поиск человека с минимальным покрытием требует $O(|P|)$ Поскольку у нас есть $|P|$ людей, общая вычислительная сложность наивной реализации составила бы $O(|E|\times|P|)=O(|P|^{2}\times|T|)$, что не масштабировалось бы на большие графы.

Вместо этого мы используем очередь с приоритетами, в которой участники упорядочиваются по эффективному покрытию (Algorithm 2, строки 2—4). Мы итеративно извлекаем участника $p$ с минимальным покрытием и, если этот участник еще не был обработан нами, добавляем его в $\pi$ (строки 7—10). Мы отмечаем участника $p$ как добавленного, получаем множество покрытых задач и множество затронутых участников, то есть участников, связанных хотя бы с одной вновь покрытой задачей (строки 11—13). Мы удаляем покрытые задачи из графа $G$ и обновляем приоритет, то есть эффективное покрытие, для затронутых участников (строки 14—16). Когда алгоритм завершает работу, мы возвращаем $\pi$ в обратном порядке, чтобы наиболее влиятельные участники оказались в начале последовательности.

Использование приоритетной очереди, выполнение которой занимает $O(\log|P|)$ операций для извлечения человека с наименьшим покрытием, обеспечивает Алгоритму 2 вычислительную сложность $O(|E|\log|P|)$.

Мы начинаем с пустого списка $\pi$ и выполняем итеративные раунды жадного удаления. В каждом раунде мы поддерживаем рабочую копию графа и многократно выбираем человека, который покрывает наибольшее количество еще не покрытых задач. Это продолжается до тех пор, пока все оставшиеся задачи в текущем раунде не будут покрыты. Как только покрытие завершено, мы удаляем выбранных людей и все ставшие изолированными задачи, а затем начинаем новый раунд на уменьшенном графе. Процесс продолжается до тех пор, пока не будут обработаны все люди.

Мы используем очередь с приоритетами и ленивыми обновлениями, где участники ранжируются по эффективному покрытию, умноженному на -1, чтобы выбирать наибольшее покрытие на каждом раунде (Алгоритм 3, строки 11—13). В начале покрытие каждого участника соответствует его степени. Алгоритм 3 останавливается, когда все участники в $G$ добавлены в $\pi$, который инициализируется пустым списком. На каждом раунде участники, добавленные в $\pi$ на предыдущем раунде, удаляются из $G$, и инициализируется очередь с приоритетами из оставшихся участников (строки 4—13). Затем Алгоритм 3 извлекает из $\mathcal{Q}$ участника $p$ с наибольшим покрытием и проверяет, актуален ли приоритет, связанный с $p$ (строки 15—17); в этом случае он добавляет $p$ в $\pi$ и отмечает задачи, с которыми связан $p$, как покрытые (строки 20—24). Если нет, он обновляет приоритет и возвращает $p$ обратно в очередь (строки 17—19). Это ленивое обновление, поскольку приоритеты участников обновляются только при необходимости.

Подобно Минимальному Покрытию, вычислительная сложность Алгоритма 3 составляет $O(|E|\log|P|)$.

Эвристика принимает граф $G$ и пороговое значение $t$ на вход и работает конструктивно. Сначала она инициализирует граф $\mathcal{U}$, который содержит только набор узлов задач и не содержит людей. На каждой итерации выбирается и добавляется в $\pi$ тот человек $p$, включение которого приводит к наименьшему возможному увеличению $\tau(G)$. Затем человек $p$ добавляется в $\mathcal{U}$ со всеми своими связями. Процесс повторяется на обновленном $\mathcal{U}$ до тех пор, пока добавление еще одного человека в него не сделает $\tau(G)>t$.

Жадная минимизация $\tau(G)$ на каждом шаге порождает серьезные вычислительные трудности. В частности, оценка предельного увеличения $\tau(G)$, вызванного добавлением человека, требует вычисления компонент связности $G$. Стандартный поиск в глубину (DFS) для компонент связности имеет стоимость $O(|P|+|T|+|E|)$. Наивная реализация жадного эвристического алгоритма выполняла бы этот поиск в глубину для каждого оставшегося человека на каждой итерации.

В результате стоимость одной итерации составляет $O(|P|\cdot(|P|+|T|+|E|))$. Поскольку этот процесс повторяется в течение $|P|$ раундов (каждый добавляет по одному человеку), общая временная сложность становится равной: $O(|P|^{2}\cdot(|P|+|T|+|E|))=O(|P|^{3}+|P|^{2}|T|+|P|^{2}|E|)$, что является неприемлемым даже для графов умеренного размера.

Именно поэтому в Алгоритме 4 мы используем структуру данных для поиска объединения с сжатием путей и объединением по рангу для эффективного отслеживания компонентов $G$ и $\tau(G)$. Кроме того, мы используем лениво обновляемую очередь с приоритетами, где мы расставляем приоритеты разработчиков по их вкладу в $\tau(G)$ и останавливаем процесс, когда $\tau(G)>t$. Функция resulting_size($\cdot$) симулирует добавление $p$ и их связей с $\mathcal{U}$ и возвращает компоненты, к которым $p$ был бы подключен после добавления (new_roots), и результирующее значение $\tau(G)$.

Используя структуру union-find, мы можем запросить $\tau(G)$ за $O(1)$ и выполнить операцию union за $O(\alpha(|T|))$, где $\alpha$ — это обратная функция Аккермана, которая растет очень медленно и на практике может считаться константой. Следовательно, отслеживание связанных компонентов на протяжении всего процесса требует $|E|$ операций union. Поэтому вычислительная сложность Алгоритма 4 в среднем составляет $O(|E|\log|P|)$. Однако, если $G$ плотный, добавление человека может привести к обновлению всех оставшихся людей в $\mathcal{Q}$, требуя $O(|P|^{2})$ обновлений. Таким образом, в худшем случае вычислительная сложность Алгоритма 4 составляет $O(|P|^{2}\log|P|)$.

Именно поэтому мы предлагаем объединить алгоритм 4 с одной из ранее рассмотренных эвристик, используя небольшой порог $t$ для приближенной оценки показателя bus factor $\mathcal{P}(G)$.

Мы предлагаем вычислить частичный порядок $\pi_{r}$ с помощью алгоритма 4 с небольшим порогом (таким как $t=0.01\times|T|$), а затем использовать минимальное покрытие или максимальное покрытие на графе $G=(\{P\setminus\pi_{r}\},T,E)$ для вычисления частичного порядка $\pi_{l}$. Итоговый порядок задается выражением $\pi=[\pi_{l}|\pi_{r}]$. На рисунке 2 мы показываем эффективность такой стратегии. Мы сгенерировали двудольный степенной граф с помощью алгоритма 1, установив $|P|=|T|=1000$, $\lambda_{P}=\lambda_{T}=0.5$ и $k_{P}=k_{T}=10$, и аппроксимировали кривую затухания $\tau(G)$ с помощью как минимального покрытия, так и максимального покрытия, варьируя порог $t$. Помня, что $\mathcal{P}(G)$ представляет собой площадь под кривой затухания $\tau(G)$, мы можем заметить, что применение этой смешанной стратегии оправдывает себя для обеих эвристик.

Для $t=0$, то есть исходной эвристики без применения алгоритма 4, мы наблюдаем наибольшую площадь под кривой (0,4 для минимального покрытия и 0,46 для максимального покрытия). По мере увеличения значения $t$ можно заметить, что площадь под кривой уменьшается. Например, для $t=10$ мы получаем площадь под кривой 0,35 для минимального покрытия и 0,37 для максимального покрытия. Однако бесконечное увеличение порогового значения $t$ не обязательно приводит к улучшениям: для минимального покрытия площадь под кривой остается равной 0,35 как для $t=50$, так и для $t=100$, в то время как для максимального покрытия площадь под кривой остается равной 0,36 как для $t=50$, так и для $t=100$. Таким образом, выбор слишком высокого порогового значения $t$, скорее всего, потребует лишь больших вычислительных затрат, не давая никаких преимуществ по сравнению с меньшими пороговыми значениями..

В заключение отметим, что для $t=|T|$ алгоритм 4 завершает работу, когда обработаны все люди из $P$; однако, как станет ясно из наших экспериментов в разделе 5, такое неограниченное применение алгоритма 4 уступает предложенной здесь смешанной стратегии..

Мы используем Алгоритм 1 для генерации 1000 двудольных графов, используя процесс выборки по степенному закону с параметрами, выбранными равномерно и случайно из следующих диапазонов:

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

Мы оцениваем эвристики как на $A(G,t)$, с $t=0.5$, как указано Avelino et al.(Avelino et al., 2016), так и на $\mathcal{P}(G)$. Для $A(G,0.5)$ мы сравниваем Minimum Coverage, Maximum Coverage, удаление по степени и базовую жадную эвристику, которая удаляет на каждом шаге человека, изолирующего наибольшее число задач (называемую greedyI). Для $\mathcal{P}(G)$ мы сравниваем Minimum Coverage и Maximum Coverage, дополненные жадной минимизацией $\tau(G)$ (с $t=10$), удаление по степени и несвязанную версию жадной минимизации $\tau(G)$ (называемую greedyτ). Мы также рассматриваем простой ансамблевый метод: $\texttt{combined}=\min(\text{min\_cov},\text{max\_cov})$.

Поскольку эти эвристики вычисляют верхние оценки, более низкие значения строго лучше. Чтобы количественно оценить относительную производительность, мы вычисляем: процент графов, для которых каждая эвристика возвращает наилучшую оценку (то есть наименьший показатель), а также среднее, минимальное и максимальное значения коэффициента зазора, где коэффициент зазора определяется как $s/s^{*}$, где $s$ — это оценка эвристики, а $s^{*}$ — наилучшая оценка, полученная среди всех эвристик для данного экземпляра.

В таблице 1 обобщены результаты. Мы наблюдаем, что Минимальное покрытие (min_cov) в целом является наиболее эффективным эвристическим методом, находят наименьшее значение в 83.6% случаев для $A(G,0.5)$ и в 78.7% случаев для $\mathcal{P}(G)$. Он также характеризуется наименьшим средним соотношением разрывов. Максимальное покрытие (max_cov) находит лучшее решение в 6.6% случаев для $A(G,0.5)$ и в 13.2% случаев для $\mathcal{P}(G)$, отличаясь наименьшим максимальным соотношением разрывов для $A(G,0.5)$. Примечательно, что эвристика степени никогда не находит лучшее решение и характеризуется наибольшим средним соотношением разрывов (за исключением greedyI для $A(G,0.5)$).

Базовый жадный алгоритм greedyI, несмотря на поиск лучшего решения в 9.8% случаев, демонстрирует худшее соотношение разрыва. Также эвристический алгоритм greedyτ не впечатляет на $\mathcal{P}(G)$, показывая лишь немного лучшую производительность, чем эвристика степени, несмотря на свои вычислительные затраты. Низкая производительность этих двух жадных эвристик иллюстрирует сложность аппроксимации bus-factor, поскольку две естественные жадные эвристики, разработанные для решения своей конкретной целевой функции, в целом работают хуже (или в лучшем случае наравне) универсальной эвристики, такой как степень.

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

Первый заметный результат заключается в том, что минимальное покрытие в значительной степени нечувствительно к структуре графа. Для меры $A(G,t)$ коэффициент несоответствия никогда не демонстрирует корреляцию (по абсолютной величине) более 0,3 ни с одним структурным признаком, что указывает на высокую надежность. Для меры $\mathcal{P}(G)$ возникают две умеренные отрицательные корреляции: с ассоритивность степеней $r(G)$ (по Пирсону $p=-0.52$) и с максимальной степенью персоны $k_{P}$ ($p=-0.35$). Такое поведение согласуется с предыдущими результатами в литературе по надежности сетей, где более высокая корреляция степеней связана с повышенной надежностью (Newman, 2003; Li et al., 2005; Artime et al., 2024; Piccolo et al., 2025). Отрицательная корреляция с $k_{P}$ также отражает тот факт, что минимальное покрытие отдает приоритет узлам с высокой степенью на ранней стадии последовательности удаления, что приводит к меньшей ошибке в графах с индивидами высокой степени..

Сравнение между минимальным покрытием и максимальным покрытием выявляет взаимодополняющее поведение. Коэффициент разрыва минимального покрытия положительно коррелирует с количеством листовых задач и максимальной степенью задачи $k_{T}$, а также отрицательно коррелирует с количеством листовых исполнителей и $k_{P}$. Максимальное покрытие, с другой стороны, демонстрирует противоположную закономерность: его ошибка положительно коррелирует с $k_{P}$ и количеством листовых исполнителей, а также отрицательно коррелирует с $k_{T}$ и количеством листовых задач..

Более того, Maximum Coverage не коррелирует с ассортативностью по степени, что дополнительно отличает его от Minimum Coverage. Эти результаты показывают, что, хотя графы с большим количеством листовых задач и асимметричным распределением степеней задач создают сложности для Minimum Coverage, они благоприятны для Maximum Coverage. И наоборот, конфигурации с большим количеством листовых узлов-людей препятствуют Maximum Coverage, но не Minimum Coverage. Эта структурная взаимодополняемость служит веским доводом в пользу совместного использования данных эвристик..

Жадные эвристики проявляют большую чувствительность к структуре: greedyτ работает хорошо, когда количество листовых людей и $k_{P}$ велики. В графах, где greedyτ дает наилучшую оценку, количество листовых людей в среднем в три раза больше, чем листовых задач, а $k_{P}$ примерно в два раза больше $k_{T}$. Эти условия позволяют greedyτ эффективно изолировать компоненты при удалении узлов.

Напротив, greedyI испытывает трудности в таких сценариях. Наличие большого числа конечных людей, каждый из которых связан с отдельной задачей, ограничивает способность эвристики изолировать несколько задач за итерацию, что приводит к завышенным оценкам bus factor. Мы обнаруживаем, что greedyI работает лучше всего в графах с большим количеством конечных задач и высокой степенью асимметрии степеней задач. В подмножестве с наилучшими результатами число конечных задач в среднем в семь раз превышает число конечных людей, а $k_{T}$ более чем в два раза превышает $k_{P}$.