Теория и практика вычисления bus-factor

Зазворка и др. [31] первыми рассмотрели задачу вычисления фактора автобуса и определили следующее семейство мер:

с функцией агрегации $\alpha\in\{\mathrm{min,max,avg}\}$ и $0<t\leq 1$. Следовательно, $\mathrm{cov}_{\alpha}(G,k)$ указывает на минимальное, максимальное или среднее покрытие $G$ — то есть минимальное/максимальное/среднее число задач, которые все еще покрыты — после удаления любого подмножества из $k$ человек. Поскольку $Z_{\mathrm{avg},t}(G)$ оказалось неадекватным [13], мы не рассматриваем его здесь и ограничиваем наш анализ $Z_{\mathrm{min},t}(G)$ и $Z_{\mathrm{max},t}(G)$. Интуитивно, Ур. 1 определяет bus-factor в терминах структурно избыточных людей, которые могут покинуть проект без ущерба для него. Чем выше число структурно избыточных людей, тем выше bus-factor.

Авелино и др. [5], напротив, неформально определили bus-factor как наименьшее число людей, уход которых изолирует более чем долю $t$ задач, где $t$ представляет собой пороговое значение, определяющее, когда проект считается застопорившимся. Мы формализуем определение Авелино и др. как задачу поиска Минимального критического множества, определяемого следующим образом:

где $0<t<1$ и $\phi(G)$ возвращают количество изолированных задач в $G$. Обратите внимание, что уравнение 2 отражает неформальное представление о том, что bus-factor — это минимальное число людей, которые должны стать недоступными, чтобы проект остановился. Чем больше минимальный критический набор, тем выше bus-factor.

Теперь мы доказываем следующее соотношение между $Z_{\min,t}(G)$ и $MCS_{t}(G)$.

Обратите внимание, что $Z_{\min,t}(G)$ также определен для $t=1$, то есть это минимальное число людей, которых нужно удалить, чтобы оставшееся покрытие стало меньше $m$. Этот случай не представляет особого интереса и легко решается, так как в нем требуется изолировать отдельную задачу с помощью минимального количества людей, а именно задачу с наименьшей степенью..

Теперь мы готовы доказать, что вычисление минимального критического множества является NP-сложным.

Как следствие предложения 1, в дополнение к минимальному критическому множеству нам нужно рассмотреть только $Z_{\max,t}(G)$, которое моделирует наилучший сценарий путем определения максимального количества людей, которые могут безопасно стать недоступными, не обнажая (то есть не изолируя) более $t\%$ задач. Мы формулируем эту величину как следующую задачу о максимальном избыточном множестве на двудольном графе:

Обратите внимание, что MRS, определенный в ур. 3, при $t=1$ запрашивает множество, которое является дополнением Минимального покрытия множества. Покрытие множества допускает естественное представление в виде двудольного графа $G=(P,T,E)$, где множество $P$ соответствует $\mathcal{F}$, множество $T$ соответствует универсуму $U$, а ребра между $P$ и $T$ кодируют покрытие каждого подмножества в $\mathcal{F}$: $E=\{(i,j)\mid i\in P,\ j\in T,\ \text{and }j\in s_{i}\text{ for some }s_{i}\in\mathcal{F}\}$.

Аналогично, для порогового значения $0<t<1$, задача MRS запрашивает множество, которое является дополнением частичного покрытия множествами. Учитывая универсум $U=\{u_{1},u_{2},\dots,u_{m}\}$ из $m$ элементов, семейство $\mathcal{F}=\{S_{1},S_{2},\dots,S_{n}\}$ из $n$ подмножеств $S_{i}\subseteq U$ таких, что $\bigcup_{i}S_{i}=U$, положительное целое число $k$ и вещественное число $0<t<1$, задача частичного покрытия множествами спрашивает, существует ли подмножество $X\subseteq\mathcal{F}$ с $|X|\leq k$ такое, что $\left|\bigcup_{X_{i}\in X}X_{i}\right|\geq tm$. Теперь мы доказываем следующие результаты.

Оба метода (MCS и MRS) игнорируют внутреннюю структуру проекта, рассматривая участников исключительно с точки зрения покрытия задач. Это мешает им учитывать роль интеграторов [22], которые с топологической точки зрения соответствуют узлам-якорям в двудольных графах (и гиперграфах), то есть узлам, удаление которых приводит к фрагментации сети [28].

Аналогичным образом, MCS и MRS предполагают, что задача может быть выполнена до тех пор, пока есть хотя бы один человек, способный ее закрыть. С точки зрения управления рисками и проектами, это нереалистичное упрощение подразумевает, что можно увеличить bus-factor проекта, просто добавив синглтоны (то есть людей, связанных только с одной задачей) для каждой задачи, что в реальных проектах встречается крайне редко [18].

На самом деле можно убедиться, что обе метрики присваивают высокий bus-factor проекту, представленному графом из несвязных диад (то есть один человек, связанный с одной задачей). Мы экспериментально продемонстрируем этот недостаток в разделе 7. Кроме того, обе метрики опираются на произвольный порог $t$ (обычно устанавливаемый на уровне 0.5) для определения условия остановки проекта; следовательно, значение bus-factor проекта зависит от $t$. Наконец, MCS и MRS не нормализованы, что делает их зависимыми от размера проекта и затрудняет содержательное сравнение между проектами..

Следовательно, в следующем разделе, опираясь на нашу предыдущую работу [24], мы представляем новое определение bus-factor, которое преодолевает вышеупомянутые недостатки.

Мы основываем нашу метрику на максимальном числе связанных задач, то есть наибольшем числе задач, содержащихся в одной компоненте связности. Как уже иллюстрируется на рис. 1, использование максимального числа связанных задач позволяет нам учесть роль интеграторов, поскольку оно отражает как охват задач, так и связность. Кроме того, вычисляя площадь под кривой затухания максимального числа связанных задач по мере постепенного удаления людей, мы устраняем необходимость определения явных условий остановки и, тем самым, избавляемся от зависимости от произвольных пороговых значений (Раздел 4.2). Наконец, нормируя эту площадь на теоретический максимум, полученный для полностью связного двудольного графа с тем же количеством участников и задач, мы получаем метрику, которую можно интерпретировать двумя способами: (1) как относительную робастность проекта по отношению к максимально возможной и (2) как ожидаемое число людей, удаление которых поставит проект под угрозу, получаемое путем умножения нормированного bus-factor на общее число участников в проекте.

Перед тем как формально определить нашу меру, мы вводим понятие бэкбон множества.

Интуитивно понятная опорная структура содержит интеграторов проекта. Чем меньше опорная структура, тем меньше фактор автобуса проекта и, следовательно, тем уязвимее проект. Тем не менее, нас интересует не только мощность опорной структуры проекта; скорее, мы сосредоточены на максимальном количестве связанных задач по мере того, как люди из опорной структуры последовательно удаляются из проекта. Обратите внимание, что (1) набор несвязанных звезд представляет собой именно ту конфигурацию, для которой MCS и MRS терпят неудачу, и (2) как только $G$ сведен к совокупности несвязанных звезд, максимальный ущерб проекту наносится удалением людей в порядке убывания их степени.

Пусть $\pi=(p_{1},p_{2},\dots,p_{k})$ — это порядок удаления такой, что множество $S=\{p\mid p\in\pi\}$ является базовым множеством размера $k$. Пусть $G^{\pi}_{i}=G[P\setminus\{p_{1},p_{2},\dots,p_{i}\}]$, при $G^{\pi}_{0}=G$, и пусть $\tau(G)$ обозначает максимальное число связанных задач в $G$. Мы измеряем площадь под кривой затухания $\tau(G^{\pi}_{i})$ для $i=1,\dots,k$ как

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

Теперь мы покажем, что вычисление робастности двудольной сети, как определено в ур. 5, является NP-сложным.

Наша мера надежности $\mathcal{R}(G)$ обобщает широко используемую меру надежности сети для неориентированных графов, предложенную Шнайдером и др. [26]. Чжао и др. [32] отметили, что установление вычислительной сложности меры надежности, предложенной Шнайдером и др., все еще остается открытой проблемой. Теорема 3 разрешает эту открытую проблему.

Меры в ур. 4 концептуально связаны с понятием естественной связности двудольного графа [27], спектральной мерой, которая отражает избыточность альтернативных путей в сети. Естественная связность является более подходящей мерой надежности, когда необходимо учитывать потоки и длину путей. Однако в случае bus-factor мы не имеем дело с потоками в сети; поэтому измерение максимального числа связанных задач является более подходящим. Кроме того, вычисление естественной связности обходится дороже, чем вычисление максимального числа связанных задач, поскольку оно зависит от всех собственных значений матрицы смежности $G$.

Наконец, мы вводим нашу нормированную мера фактора автобуса как отношение между робастностью двудольного графа $G$, вычисленной с последовательностью удаления $\pi\in\Pi(P)$ (где $\Pi(P)$ обозначает множество всех возможных перестановок людей в $P$), и робастностью полносвязного двудольного графа того же размера:

Обратите внимание, что в Ур. 6 мы используем формулировку, немного отличающуюся от формулировки сетевой устойчивости в Ур. 4. Это просто два разных способа оценки площади под кривой: Ур. 4 соответствует сумме Гаусса, в то время как Ур. 6 применяет метод трапеций, который обеспечивает более точную оценку площади под кривой. Нормализованный bus-factor $\mathcal{B}(G,\pi)$ принимает значения в $[0,1]$ и может интерпретироваться как доля устойчивости проекта относительно теоретического максимума, что позволяет проводить сравнения между проектами. Например, bus-factor, равный $\mathcal{B}(G,\pi)=0.5$, указывает на то, что $G$ вдвое менее устойчив, чем полностью связанный граф того же размера.

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

В разделе 4.1 мы показали, что избыточное множество является дополнением частичного покрытия множества; следовательно, любой приближенный алгоритм для задачи минимального частичного покрытия множества дает приближенный алгоритм для задачи поиска максимального избыточного множества. Наилучший возможный полиномиально-сложностной приближенный алгоритм для задачи покрытия множества, если только P$=$NP, гарантирует решение, которое превосходит оптимальное решение [9] не более чем в $O(\log m)$ раз. Тот же алгоритм с такими же гарантиями производительности может быть использован для приближенного решения задачи частичного покрытия множества, поскольку обе задачи могут рассматриваться как частные случаи субодиномического покрытия множества [29].

Напомним, что MRS принимает на вход граф $G=(P,T,E)$ и вещественное число $0<t\leq 1$ и возвращает наибольшее множество людей, которые покрывают менее $tm$ задач. Концептуально наш приближенный алгоритм работает следующим образом: на каждой итерации человек, покрывающий наибольшее количество в настоящее время непокрытых задач, добавляется в множество $S$ до тех пор, пока не будет покрыто более $tm$ задач. Поскольку $S$ является приближенным решением задачи минимального частичного покрытия множества, множество $X=P\setminus S$ представляет собой приближенное решение для MRS. Применяя метод, предложенный Lim и др. [19], мы представляем приближенный алгоритм для MRS за почти линейное время, который масштабируется до очень больших двудольных графов (Алгоритм 1⟧).

В нашем алгоритме мы используем очередь с приоритетами $\mathcal{Q}$ для планирования человека с наибольшим покрытием задач, а набор покрытых задач и множество $S$ мы представляем в виде битовых массивов (алгоритм 1, строки 2–4). Для каждого человека мы отслеживаем непокрытые задачи в непрерывном массиве сегментов $\mathcal{I}$ и приоритизируем людей по их степени (строки 5–8). На каждой итерации мы извлекаем человека $p$ из $\mathcal{Q}$ и проверяем, равен ли их приоритет текущему количеству непокрытых задач, effective_coverage (строки 9–13). Если это так, мы добавляем $p$ в частичное покрытие множества $S$ и обновляем набор покрытых задач (строки 13–16); в противном случае мы возвращаем $p$ обратно в очередь с обновленным приоритетом и покрытием задач (строки 16–19). Когда количество покрытых задач достигает как минимум $tm$, цикл завершается, и алгоритм возвращает множество $P\setminus S$ вместе с его мощностью в качестве решения MRS (строки 20–22).).

Алгоритм 1 представляет собой $O(n)$-приближение для MRS. Следующая теорема показывает, что это отношение приближения является наилучшим достижимым с помощью полиномиального алгоритма, если только $\mathrm{P}=\mathrm{NP}$.

Для аппроксимации минимального критического множества мы предлагаем подход на основе перколяции узлов, при котором люди постепенно удаляются из графа в соответствии с порядком удаления $\pi$. Мы инициализируем массив, содержащий количество людей, покрывающих каждую задачу, то есть их степень (Алгоритм 2, строки 2–4). По мере удаления людей из $G$ мы уменьшаем степень задач, с которыми они связаны (строки 6–9), обновляем счетчик изолированных задач, когда задача $\mathfrak{t}$ становится изолированной (строки 10–12), и отслеживаем количество удаленных людей (строки 13–14). Когда количество изолированных задач превышает $tm$ (при этом $t$ обычно устанавливается равным $0.5$ [5]), алгоритм завершается, возвращая мощность MCS (строки 15–17).

Алгоритм 2 масштабируется линейно по количеству ребер, поскольку ему приходится обрабатывать каждого человека и связанные с ним задачи не более одного раза, что приводит к вычислительной сложности $O(|E|)$. Поскольку алгоритм 2 в качестве входных данных ожидает порядок удаления $\pi$, естественным является вопрос о том, как выбрать $\pi$. Разумным выбором является удаление людей в порядке убывания степени (как это сделали Авелино и др. [5]), что, как правило, хорошо работает на практике. Фактически, реальные сети являются разреженными и демонстрируют распределения степеней с тяжелыми хвостами: относительно немногие узлы имеют высокую степень, в то время как подавляющее большинство имеет низкую степень [2]. Эта характеристика означает, что узлы с высокой степенью имеют первостепенное значение для связности сети. Например, Шан показал, что в двудольных графах удаление относительно небольшой доли узлов с высокой степенью существенно снижает естественную связность сети [27].

Хотя удаление по степени на практике работает хорошо по вышеупомянутым причинам, теперь мы показываем, что этот порядок удаления обеспечивает в худшем случае $O(n)$-аппроксимацию для минимального критического множества.

Иными словами, в худшем случае порядок удаления по степени людей может дать минимальный критический набор размером до $n-1$ человек, в то время как оптимальное значение составляет всего $1$⟧.

Вычисление надежности требует, при удалении людей из $G$, итерации по всем связанным компонентам в $G$, подсчета содержащихся в них задач и выбора максимума среди них. Наивная реализация этого процесса, основанная на $n$ повторяющихся применениях поиска в глубину (DFS), привела бы к алгоритму, масштабируемому квадратично по количеству людей, с вычислительной сложностью $O(n^{2}m)$.

Здесь мы предлагаем эффективную реализацию этого процесса путем отслеживания максимального количества связанных задач с использованием структуры данных Union–Find: структуры непересекающихся множеств, в которой каждое множество представлено в виде дерева, а корень дерева является репрезентативным элементом множества. Когда два множества объединяются, корни соответствующих деревьев соединяются [9]. Если вместо удаления людей мы добавляем их в обратном порядке удаления, эта структура данных позволяет отслеживать максимальное количество связанных задач по мере роста компонентов. Эта идея приводит к следующему алгоритму за линейное время22 2 Тот же алгоритм может быть использован для вычисления надежности любой произвольной сети., с вычислительной сложностью $O(|E|)$.

Алгоритм 3 принимает на вход граф $G$ и последовательность удаления $\pi$. Мы инициализируем структуру данных Union–Find $\mathcal{U}$ с $m$ непересекающимися задачами (строка 2) и обрабатываем последовательность удаления $\pi$ в обратном порядке, от последнего удаляемого человека к первому (строка 4). Каждый раз, когда мы обрабатываем человека $p$, мы объединяем компоненты, соответствующие задачам, с которыми связан $p$ (строки 5–6), и сохраняем в векторе tau максимальное количество связанных задач в $\mathcal{U}$ (строка 7). Наконец, bus-factor $\mathcal{B}$ вычисляется путем применения уравнения 6 к вектору tau.

Удаление людей по степени снова предлагает хорошее приближение надежности двудольных сетей на практике. Пикколо и др. эмпирически продемонстрировали эффективность удаления на основе степени при изучении надежности реального проекта, связанного со строительством электростанции на биомассе [22]. Шанг [27], напротив, подтвердил с помощью симуляций предсказания теории протекания на двудольных сетях относительно удаления узлов высокой степени и впоследствии расширил теорию, введя концепцию якорных узлов [28], которые тесно связаны с нашим понятием интеграторов.

Хотя удаление по степени хорошо работает на практике, мы докажем, что в худшем случае оно дает $O(n)$-аппроксимацию надежности сети.

Мы отмечаем, что Теорема 6 устанавливает $O(n)$ худшую оценку приближения не только для фактора автобуса, но и для устойчивости сети в целом (включая недвудольные графы).

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

Назначение большего количества задач людям — распространенная стратегия увеличения знаний персонала внутри организации, что делает проект менее уязвимым к недоступности участников [22]. В рамках нашего графо-теоретического подхода это соответствует добавлению ребер в исходную двудольную сеть, что делает граф более связанным и, следовательно, более устойчивым. И наоборот, удаление ребер моделирует ситуации, в которых людям назначается в среднем меньше задач, что приводит к менее устойчивой структуре проекта.

Мы ожидаем, что хорошо спроектированная мера bus factor будет положительно коррелировать с плотностью сети: чем плотнее сеть, тем надежнее проект; чем разреженнее сеть, тем менее надежным он становится. Мы выполняем этот набор симуляций, добавляя или удаляя ребра из исходной сети батчами по $100$, в общей сложности для $50\,000$ добавленных или удаленных ребер.

Мы обнаруживаем, что MRS в значительной степени нечувствительна к вариациям плотности сети, в то время как MCS и Robustness качественно демонстрируют ожидаемое поведение (Рис. 4). Однако этот эксперимент уже подчеркивает последствия зависимости MCS от фиксированного порога. По мере того как сеть становится более плотной, MCS насыщается раньше, чем Robustness (Рис. 4A): в течение первых добавленных ребер $25\,000$ MCS растет быстрее, чем Robustness, а затем выходит на плато (см. вставку на Рис. 4A). Это поведение является прямым следствием порогового параметра $t$.

Аналогично, в то время как MCS и Robustness уменьшаются с сопоставимой скоростью по мере разрежения сети (рис. 4B), MCS демонстрирует заметные колебания (см. врезку на рис. 4B). Эти колебания возникают как из-за использования фиксированного порога, так и из-за того, что разрежение сети изменяет степени вершин и, как следствие, порядок удаления. Напротив, Robustness демонстрирует более стабильное поведение, поскольку оно основано на компонентах связности и максимальном числе связанных задач, а не только на покрытии задач.

В целом, этот эксперимент уже демонстрирует преимущества оценки фактор-буса проекта с использованием робастности по сравнению с альтернативами на основе покрытия.

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

Тем не менее, найм не является панацеей, и при плохой реализации эта стратегия может дать обратный результат. Во-первых, сам процесс найма является сложным, ограниченным по бюджету и часто медленным, неэффективным или нерезультативным [6]. Во-вторых, привлечение новых людей к проекту может повлечь за собой более высокие затраты на координацию между сотрудниками [7]. Наконец, существует существенная разница с точки зрения робастности проекта между добавлением интеграторов и добавлением специалистов (то есть людей, работающих только над несколькими задачами): как уже упоминалось, именно интеграторы в первую очередь повышают глобальную робастность проекта [22].

Мы моделируем эти две стратегии путем добавления одиночных элементов или дубликатов группами по $100$ человек и представляем результаты на рис. 5. Мы обнаружили, что как MRS, так и MCS чрезмерно чувствительны к добавлению одиночных элементов (рис. 5A). Обе метрики растут без ограничений, что подразумевает, что bus-factor проекта можно увеличивать бесконечно, просто добавляя одиночные элементы. Этот результат резко противоречит эмпирическим данным об организационной дифференциации [18], игнорировании координации в организациях [14] и динамике итеративной работы [23], что подчеркивает существенное ограничение метрик bus-factor, основанных на MRS и MCS..

Напротив, робастность снижается при добавлении одиночных узлов в проект (рис. 5A). Это снижение является прямым следствием как ее зависимости от максимального числа связанных задач, так и ее нормировочного коэффициента (уравнение 6). Поскольку робастность отражает степень фрагментации проекта при уходе людей, одиночные узлы не могут увеличить ее значение. Более того, поскольку робастность нормирована, добавленные одиночные узлы фактически рассматриваются как потерянные ресурсы по сравнению с вкладом, который мог бы внести интегратор. Соответственно, количество людей, необходимых для дестабилизации проекта, остается стабильным на протяжении всего моделирования (на врезке к рис. 5A), что дополнительно подчеркивает гибкость и двойную интерпретируемость робастности..

MRS также относительно нечувствителен к дубликатам, в то время как MCS насыщается и не отражает убывающую отдачу, связанную с добавлением дубликатов (Рис. 5B). И снова Robustness успешно отражает убывающую отдачу, обеспечиваемую людьми с постепенноdecreasing степенью, увеличиваясь более плавно, чем MCS, и в конечном итоге уменьшаясь, когда дополнительные люди больше не вносят значимый вклад в избыточность — нюанс, который MCS не способен представить.

В целом, этот эксперимент демонстрирует, что MRS и MCS плохо подходят в качестве мер bus-factor, так как они переоценивают влияние одиночных разработчиков и недооценивают важность интеграторов. Напротив, Robustness точно отражает эффекты как одиночных разработчиков, так и интеграторов, демонстрируя поведение, согласующееся с теоретическими ожиданиями и эмпирическими данными.

Перераспределение сотрудников по задачам без найма нового персонала или изменения исходного распределения рабочей нагрузки является еще одной эффективной стратегией повышения устойчивости проекта. Пикколо и др. [24], например, разработали две эвристики, которые увеличили bus-factor проекта биомассовой электростанции на $40\%$.

Здесь мы используем хорошо зарекомендовавший себя результат из network science, который связывает network robustness с корреляцией степеней (также известной как degree assortativity) [21]. Degree correlation измеряет степень, в которой узлы с высокой (низкой) степенью склонны соединяться с другими узлами с высокой (низкой) степенью. Она определяется как коэффициент корреляции Пирсона для степеней на обоих концах ребра:

В этой серии экспериментов мы оцениваем реакцию мер фактора автобуса на синтетических сетях с различными уровнями корреляции степеней, сохраняя при этом неизменными количество людей, количество задач и их распределения степеней.

Достижение этого требует нетривиальной процедуры выборки. Мы выполняем выборку статистического ансамбля $\{G\}$ в соответствии с вероятностной мерой $\mu(G)\propto e^{-H(G)}$, индуцированной гамильтонианом $H(G)=-J\sum_{(i,j)\in E}k_{i}k_{j}$, где $J$ представляет собой параметр, управляющий корреляцией степеней выбранных сетей.

Процедура сэмплирования заключается в применении динамики Метрополиса к исходному графу $G$ путем многократного переподключения двух случайно выбранных ребер $(u,z)$ и $(w,v)$, что приводит к созданию новой пары ребер (которых еще нет в сети) $(u,v)$ и $(w,z)$. Для полученной сети $G^{\prime}$ мы вычисляем разность энергий $\Delta H=H(G^{\prime})-H(G)$ и принимаем $G^{\prime}$ с вероятностью $e^{-\Delta H}$. Мы исследуем $17$ равноудаленных значений $J$ на интервале $[-0.002,0.002]$, генерируя $100$ независимых сетей для каждого значения, что в сумме составляет $1\,700$ сетей.

Как показано на вставке на рис. 6A, средняя корреляция степеней для выборочных сетей монотонно возрастает с $J$. Из рис. 6A мы видим, что MRS снова в значительной степени нечувствителен к изменениям в распределении людей по задачам и даже демонстрирует поведение, противоположное ожидаемому, слегка уменьшаясь по мере увеличения корреляции степеней. И MCS, и Robustness, напротив, ведут себя в соответствии с теоретическими ожиданиями и предыдущими результатами из network science [21].

Мы отмечаем, однако, что MCS вносит бо́льшие искажения в отношении корреляции степеней $r$ по сравнению с Robustness (Рис. 6B). Кривая, создаваемая Robustness, ближе к линейной и демонстрирует меньшую общую дисперсию, чем та, что создается MCS.

В данной статье мы разработали предметно-независимую теоретико-графовую структуру, которая позволяет свести задачу измерения bus-factor к комбинаторной задаче на двудольных графах. Мы определили три комбинаторные задачи, которые кодируют различные определения bus-factor: максимальное избыточное множество (MRS), минимальное критическое множество (MCS) и bus-factor как устойчивость сети (Robustness). Показав, что все три формулировки являются NP-трудными, мы продемонстрировали, что вычисление bus-factor проекта — это не просто показатель риска, актуальный для управления проектами, но и задача, имеющая важное значение для теории вычислений: если мы способны решить любую из этих трех задач за полиномиальное время, то $\text{P}=\text{NP}$. Более того, наше доказательство NP-трудности Robustness (Теорема 3) подразумевает NP-трудность вычисления показателя устойчивости сети $\mathcal{R}$, введенного Schneider et al. [26], что до сих пор оставалось открытой проблемой [32]⟧.

Наша концепция связывает сетевую науку, информатику и управление проектами. Как показывает данная статья, задачи управления проектами могут напрямую выигрывать от использования как алгоритмических, так и теоретических инструментов, разработанных в сетевой науке и теоретической информатике. Например, теория перколяции [2] дает теоретическое обоснование для удаления участников в порядке убывания степени узла, в то время как инструменты из области аппроксимационных алгоритмов позволяют нам формально рассуждать о качестве и пределах эвристических стратегий. В связи с этим наши доказательства границ аппроксимации в худшем случае (Теоремы 4, 5, 6) предоставляют, насколько нам известно, первые результаты аппроксимации для MRS, MCS, Robustness и стратегий удаления на основе степени узла. В дополнение к этому, управление проектами предлагает теории и эмпирические данные, которые мы использовали для обоснования нашего экспериментального сравнения метрик bus-factor..

Наша работа предоставляет обширную экспериментальную и теоретическую поддержку важности интеграторов как факторов, обеспечивающих робастность проекта [22], подкрепляя предыдущие выводы о программных проектах [20] и динамике итеративной разработки [23]. Эти результаты раскрывают тесную связь как с концепцией якорных узлов, так и с теорией робастности в двудольных графах и гиперграфах [28]. Более того, мы показали связь между робастностью проекта и корреляцией степеней [21], что подразумевает возможность повышения робастности проекта путем перераспределения людей по задачам. Наконец, наши масштабные тесты показали, что Robustness является единственной мерой, которая стабильно демонстрирует ожидаемое поведение, в то время как меры на основе покрытия (MRS и MCS) имеют фатальные недостатки, в частности неспособность отразить фрагментацию проекта, что делает их непригодными в качестве мер bus factor.

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

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

1. ⟦1. Надежность в настоящее время является единственной мерой bus-factor, которая согласуется с теоретическими ожиданиями и эмпирическими данными. Кроме того, она нормализована, не опирается на пороговые значения и способна отражать фрагментацию проекта — качества, которые облегчают ее использование на практике..
2. ⟦2. В случае, когда наем сотрудников осуществляется с целью повышения устойчивости проекта, наилучшей стратегией является наем интеграторов, которые увеличивают избыточность и связывают модули проекта, находящиеся на значительном удалении друг от друга..
3. ⟦3. Фактор автобуса проекта может быть улучшен за счет перераспределения людей по задачам без необходимости увеличения индивидуальной рабочей нагрузки или найма новых сотрудников. Этого можно достичь с помощью специализированных алгоритмов [24] или путем увеличения корреляции степеней двудольной сети проекта, как мы показали.
4. ⟦4. MCS не подходит в качестве меры bus factor. Тем не менее, она может быть полезной для оценки того, насколько неравномерно распределена рабочая нагрузка. Например, можно оценить меньшую группу людей, которая создала по меньшей мере $80\%$ кодовой базы, проверяя, подчиняется ли проект распределению Парето 80–20.
5. ⟦5. MRS неинформативна в качестве меры bus-factor. Однако ее дополнение, частичное покрытие множества, может быть полезно для выявления небольшого набора экспертов в предметной области и интеграторов, которые могут стимулировать практики обмена знаниями и наставлять новых сотрудников, повышая жизнеспособность проекта. Это связывает bus-factor с проблемой поиска наиболее влиятельных узлов в сети.

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

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

1. ⟦1. Мы показали NP-трудность задач MRS, MCS и Robustness, а также доказали, что задача MRS является NP-трудной для аппроксимации с коэффициентом $O(n^{1-\epsilon})$. Вопрос об аппроксимируемости задач MCS и Robustness остается открытым, и ответ на него даст нам важное понимание качества аппроксимации, которое можно ожидать от любых эвристик..
2. ⟦2. Our measure of bus-factor is only structural and does not account for relative task importance or people skills. Complementing the structural insights provided by Robustness with other social and technical factors [23] will likely offer a more complete understanding of project robustness.
3. ⟦3. Теория фактора автобуса может быть расширена как за счет развития ее теории протекания, так и за счет выявления того, какие сетевые метрики коррелируют с ним, помимо корреляции степеней.
4. ⟦4. Мы показали, что удаление вершин на основе степени хорошо работает на практике, однако алгоритмы, обеспечивающие лучшие оценки, весьма вероятно, существуют. Это перспективное направление исследований, способное обеспечить как создание более эффективных алгоритмов, так и более глубокое понимание фактора автобуса..

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