Software & Systems

Подразделения Минобрнауки России – государственного заказчика-координатора ряда федеральных целевых программ (ФЦП), а также организации, осуществляющие функции текущего управления реализацией этих программ (Дирекции), находятся в условиях постоянного увеличения массива накапливаемой и обрабатываемой информации по исполняемым государственным контрактам (ГК) [1]. По этой причине все более актуальным становится решение следующих задач:

-    выбор принципов анализа накопленной информации о реализации мероприятий ФЦП в научно-технической сфере с целью выявления фактов логической связанности информационных объектов, имеющих место при реализации ФЦП, а также их статистического анализа;

-    разработка программных средств автоматизации информационно-аналитической поддержки прогнозирования мероприятий ФЦП в научно-тех­нической сфере.

В ходе проводимого исследования авторы ведут работы по проектированию и разработке экспериментального образца Информационной системы анализа связанности сложно-структу­рированных данных (ИС АССД) ГК в научно-тех­нической сфере.

Рассматриваемые в рамках работ сложно-структурирован­ные данные, характеризующие процесс исполнения ГК (структурная схема процесса приведена на рисунке 1), содержат информацию о следующих информационных объектах: федеральная целевая программа, предложение (заявка на формирование тематики), лот, заявка, контракт, этап контракта, организация (участник размещения заказа), персона (руководитель организации-испол­нителя, руководитель работ по контракту от организации-ис­полнителя, ответственный сотрудник профильного подразделения заказчика и др.).

В результате анализа подходов к решению вышеописанных задач были сформулированы требования к ИС АССД по обеспечению поддержки выполнения следующих задач пользователей:

-    самостоятельное проведение сотрудниками подразделений государственных заказчиков-коор­динаторов и Дирекций статистического анализа данных о выбранных информационных объектах по различным параметрам/фильтрам при подготовке отчетов;

-    выявление фактов связанности однотипных и разнотипных объектов, оценка степени их связанности, анализ статистики связанности по накладываемым фильтрам в разных аспектах и т.д.;

-    визуализация результатов анализа связанности в виде двунаправленных графов.

Предполагается, что конкретный вариант использования функциональных возможностей ИС АССД и конечная смысловая интерпретация результатов статистического анализа данных должны оставаться за специалистом (однако набор предустановленных вариантов использования фильтров также будет подготовлен в ходе разработки).

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

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

Для достижения вышеописанных целей в составе функциональных возможностей ИС АССД были реализованы следующие алгоритмы теории графов:

-    алгоритм поиска в графе обособленных подграфов;

-    алгоритм проверки связанности двух произвольных объектов из совокупности данных (то есть достижимости одной вершины из другой);

-    алгоритм поиска замкнутых циклов между объектами в графе;

-    алгоритм поиска набора объектов, обладающих максимальной связанностью с другими объектами, и построение кратчайших путей их достижимости (возможно использование Лувенского метода, метода поиска k-ядра (k-core));

-    алгоритм выявления объектов, находящихся от исходного объекта в радиусе, не более заданного расстояния (возможно использование алгоритма «поиска в ширину» или матрицы достижимостей).

Представление в виде графа (построение графа в оперативной памяти), а также алгоритмы анализа графа реализуются с использованием библиотеки NetworkX (распространяется как свободное ПО по BSD-лицензии, реализована на языке Python) [2]. Визуализация графа реализуется с использованием библиотеки NetworkX и D3 [3].

Интерфейсные средства ИС АССД обеспечивают настройку процедуры построения графа и параметров визуализации графа (включая настройки фильтрации и укладки графа), а также визуализацию графа.

Интерфейсные средства ИС АССД обеспечивают настройку следующих базовых параметров построения графа связанных объектов:

-    тип графа – однородный/разнородный; в однородном графе все вершины одного типа (например организации или контракты), разнородный граф предполагает наличие вершин разного типа (например, для построения связей между лотами и организациями, подавшими заявки);

-    тип (типы) объектов ГК, которые будут представлены на графе вершинами (реализуется в виде матрицы связанных объектов, позволяющей выбрать желаемый набор типов объектов, перечисленных как наименования строк и столбцов матрицы, а также отметить признак появления связи между ними, см. пример фрагмента матрицы на рисунке 2);

-    параметры представления вершин графа (то есть указание атрибутов объекта ГК, которыми интерпретируются атрибуты вершины графа); в состав настраиваемых параметров вершин должны входить (пример для вершин типа «Организация» приведен на рисунке 3):

а)    диаметр вершины (например, диаметр вершины-организации может зависеть от количества контрактов, выполненных организацией);

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

в)     текстовая или числовая подпись к вершине (наименование организации, число выполненных контрактов, номер приоритетного направления и т.д.);

-    параметры представления связей на графе:

а)    толщина связи (например, может определяться количеством общих контрактов между связанными организациями-соисполнителями);

б)    тип линии связи (сплошная или прерывистая);

в)     учет направленности связи;

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

Смысловое содержание графа определяется вышеописанными настройками параметров построения графа. Примеры базовых вариантов построения графов:

-    граф «Организации-соисполнители», отражающий взаимодействие организаций в рамках общих контрактов;

-    граф «Организации-соисполнители–Кон­тракты» – расширенный вариант, позволяющий проанализировать характеристики связанности непосредственно в разрезе каждого общего контракта;

-    граф «Организации-участники размещения–Лоты», отражающий характеристики связанности между организациями, подающими заявки на определенные лоты.

Интерфейсные средства ИС АССД для настройки параметров визуализации графа обеспечивают:

-     возможность создания пользовательских фильтров отображения информации на графе с указанием состава параметров фильтрации и их значений, а также применение одного или нескольких (логически не противоречащих друг другу) фильтров;

-     возможность применения специализированных алгоритмов автоматической укладки графов на плоскости (например гамма-алгоритм, алгоритм GIOTTO, Sorted Grid).

Классификация возможных параметров фильтрации:

-     по временному периоду;

-     по типам информационных объектов;

-     по областям исследований и отраслевым предназначениям конкурсов и контрактов;

-     по территориальному признаку (федеральный округ, регион, город);

-     по типу организации;

-     по программному мероприятию ФЦП;

-     по приоритетному направлению развития науки, технологий и техники в Российской Федерации;

-     по критическим технологиям Российской Федерации;

-     по году заключения ГК;

-     по направлению модернизации;

-     по виду работы (например научно-иссле­довательская);

-     по состоянию (исполняется, выполнено и др.).

Пример составных фильтров:

-     сведения об участии вузов в рамках одной и/или нескольких ФЦП (сводные данные об участии вуза, группы вузов с детализацией по регионам);

-     география реализации ФЦП (активность и характеристики участия федеральных округов и регионов в реализации научно-технических проектов в рамках одной или нескольких ФЦП по определенной тематике).

Интерфейсные средства ИС АССД для анализа графа обеспечивают выбор и настройку параметров следующих алгоритмов:

-     поиск в графе обособленных подграфов (группы объектов, взаимодействующие друг с другом в замкнутом процессе, например группы организаций, работающих в рамках одного или нескольких контрактов);

-     проверка связанности двух произвольных объектов из совокупности данных (среди предварительно заданных объектов);

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

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

Интерфейсные средства ИС АССД для визуализации графа обеспечивают:

-     отображение и масштабирование графа с установленными настройками в требуемом разрезе;

-     укладку элементов графа с использованием выбранного алгоритма укладки, включая последовательное применение нескольких алгоритмов укладки;

-     фильтрацию отображаемых на экране элементов графа в зависимости от выставленных параметров фильтрации;

-     обновление результатов визуализации в соответствии с регламентом на экране пользователя (в случае наличия изменяющихся результатов аналитической обработки в оперативном режиме);

-     специализированное отображение объектов по указанным пользователями признакам: минимальное/максимальное значение указанного атрибута элемента графа (диаметр, толщина связи, степень связности и др.).

Визуализация графа организаций-соисполните­лей в рамках выполнения работ по ГК (рис. 4) позволяет:

-    визуально выявить организации с наибольшим перечнем соисполнителей в рамках всех контрактов;

-    выявить преобладающее приоритетное направление (по выполненным контрактам);

-    определить случаи с наибольшим числом общих контрактов между соисполнителями;

-    выявить тот факт, что соисполнителями в большинстве случаев становятся организации, изначально ориентированные на контракты одинакового приоритетного направления ФЦП;

-    выявить факты кооперации двух и более организаций для выполнения общих контрактов.

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

Анализ полученных промежуточных результатов работ по созданию экспериментального образца ИС АССД позволил сделать вывод о перспективности данного инструмента в качестве средства исследования накапливаемой в БД информации о реализации ФЦП при подготовке типовых сводок, отчетов, докладов, при обработке запросов об участниках ФЦП и ходе ее реализации по отдельным проектам и группам проектов, о показателях финансирования и эффективности реализации ФЦП. Дальнейшие работы направлены на расширение возможностей системы в части применения алгоритмов теории графов, а также функциональных возможностей по настройке визуализации и интерактивности графов.

Литература

1.     Горюнов И.Г., Корецкий М.В., Пономарев С.А., Сытник Д.А. Анализ связанности сложно-структурированных текстовых данных, характеризующих процессы формирования, размещения и исполнения государственных заказов в научно-технической сфере // Программные продукты и системы. 2012. № 4.

2.     NetworkX. URL: http://networkx.github.com/ (дата обращения: 28.12.2012).

3.     D3. URL: http://d3js.org/ (дата обращения: 28.12.2012).