«А. Г. Додонов, Д. В. Ландэ, В. В. Прищепа, В. Г. Путятин КОНКУРЕНТНАЯ РАЗВЕДКА В КОМПЬЮТЕРНЫХ СЕТЯХ Киев – 2013 УДК 004.5 ББК 22.18, 32.81, 60.54 C95 А.Г. Додонов, Д.В. Ландэ, В.В. Прищепа, В.Г. Путятин Конкурентная ...»
-- [ Страница 3 ] --
Важной характеристикой сети является функция распределения степеней узлов P(k ), которая определяется как вероятность того, что узел i имеет степень ki = k. Сети, характеризующиеся разными P (k ), демонстрируют различное поведение. P(k ) в некоторых случаях может быть распределениями Пуассона ( P ( k = e - m m k k !, где m – математическое ожидание), экспоненциальным ( P ( k ) = e - k / m ) или степенным ( P ( k ) ~ 1 k g, k 0, g > 0 ).
Сети со степенным распределением степеней узлов называются безмасштабными (scale-free). Именно безмасштабные распределения часто наблюдаются в реально социальных сетях. При степенном распределении возможно существование узлов с очень высокой степенью, что практически не наблюдается в сетях с пуассоновским распределением.
Расстояние между узлами определяется как количество шагов, которые необходимо сделать, чтобы по существующим ребрам добраться от одного узла до другого. Естественно, узлы могут быть соединены прямо или опосредованно. Кратчайшим путем dij между узлами i и j называется наименьшее расстояние между ними.
Для всей сети можно ввести понятие среднего пути, как среднее по всем парам узлов кратчайшего расстояния между ними:
где n – количество узлов, dij – кратчайшее расстояние между узлами i и j.
Венгерскими математиками П. Эрдёшем (P. Erds) и А. Реньи (A. Rnyi) было показано, что среднее расстояние между двумя вершинами в случайном графе растет как логарифм от числа его узлов [Erds, 1960].
Некоторые сети могут оказаться несвязными, т.е. найдутся узлы, расстояние между которыми окажется бесконечным. Соответственно, средний путь может оказаться также равным бесконечности. Для учета таких случаев вводится понятие среднего инверсного пути (его еще называют «эффективностью сети») между узлами, рассчитываемое по формуле:
Сети также характеризуются таким параметром как диаметр или максимальный кратчайший путь, равный максимальному значению из всех d ij.
Д. Уаттс (D. Watts) и С. Строгатц (S. Strogatz) в 1998 году определили такой параметр сетей, как коэффициент кластерности [Watts, 1998], который характеризует уровень связности узлов в сети, тенденцию к образованию групп взаимосвязанных узлов, так называемых клик (clique). Кроме того, для конкретного узла коэффициент кластеризации показывает, сколько ближайших соседей данного узла являются также ближайшими соседями друг для друга.
Коэффициент кластерности может определяться как для каждого узла, так и для всей сети. Для сети коэффициент кластерности определяется как нормированная по количеству узлов сумма соответствующих коэффициентов для отдельных узлов.
Коэффициент кластерности для отдельного узла сети определяется следующим образом. Пусть из узла выходит k ребер, которые соединяют его с k другими узлами, ближайшими соседями.
Если предположить, что все ближайшие соседи соединены непосредственно друг с другом, то количество ребер между ними соk (k - 1). Т.е. это число, которое соответствует максиставляло бы мально возможному количеству ребер, которыми могли бы соединяться ближайшие соседи выбранного узла. Отношение реального Конкурентная разведка в компьютерных сетях количества ребер, которые соединяют ближайших соседей данного узла к максимально возможному (такому, при котором все ближайшие соседи данного узла были бы соединены непосредственно друг с другом) называется коэффициентом кластерности узла i - C (i). Естественно, эта величина не превышает единицы.
Посредничество (betweenness) – это параметр, показывающий, сколько кратчайших путей проходит через узел. Эта характеристика отражает роль данного узла в установлении связей в сети. Узлы с наибольшим посредничеством играют главную роль в установлении связей между другими узлами в сети. Посредничество bm узла m определяется по формуле:
где B(i, j ) – общее количество кратчайших путей между узлами i и j, B(i, m, j ) – количество кратчайших путей между узлами i и j, проходящих через узел m.
О «структуре сообщества» можно говорить тогда, когда существуют группы узлов, которые имеют высокую плотность ребер между собой, притом, что плотность ребер между отдельными группами – низкая. Традиционный метод для выявления структуры сообществ – кластерный анализ. Существуют десятки приемлемых для этого методов, которые базируются на разных мерах расстояний между узлами, взвешенных путевых индексах между узлами и т.п. В частности, для больших социальных сетей наличие структуры сообществ оказалось неотъемлемым свойством.
К свойствам реальных социальных сетей относятся и так называемые «слабые» связи. Аналогом слабых социальных связей являются, например, отношения с далекими знакомыми и коллегами.
В некоторых случаях эти связи оказываются более эффективными, чем связи «сильные». Так, группой исследователей из Великобритании, США и Венгрии, был получен концептуальный вывод в области мобильной связи, заключающийся в том, что «слабые» социальные связи между индивидуумами оказываются наиболее важными для существования социальной сети [Bjorneborn, 2004].
Для исследования были проанализированы звонки 4.6 млн.
абонентов мобильной связи, что составляет около 20 % населения одной европейской страны. Это был первый случай в мировой практике, когда удалось получить и проанализировать такую больСоциальные сети шую выборку данных, относящихся к межличностной коммуникации.
В социальной сети с 4.6 млн. узлов было выявлено 7 млн. социальных связей, т.е. взаимных звонков от одного абонента другому и обратно, если обратные звонки были сделаны на протяжении 18 недель. Частота и продолжительность разговоров использовались для того, чтобы определить силу каждой социальной связи.
Было выявлено, что именно слабые социальные связи (одиндва обратных звонка на протяжении 18 недель) связывают воедино большую социальную сеть. Если эти связи проигнорировать, то сеть распадется на отдельные фрагменты. Если же не учитывать сильных связей, то связность сети нарушится (рис. 34). Оказалось, что именно слабые связи являются тем феноменом, который связывает сеть в единое целое.
1) полная карта сети социальных коммуникаций; 2) социальная сеть, из которой изъяты слабые связи; 3) сеть, из которой изъяты сильные Несмотря на огромные размеры некоторых социальных сетей во многих из них существует сравнительно короткий путь между двумя любыми узлами – геодезическое расстояние. В 1967 г. психолог С. Милгран в результате проделанных масштабных экспериментов вычислил, что существует цепочка знакомств, в среднем длиной шесть звеньев, практически между двумя любыми гражданами США [Milgram, 1967].
Д. Уаттс и С. Строгатц обнаружили феномен, характерный для многих реальных сетей, названный эффектом малых миров (Small Worlds) [Watts, 1998]. При исследовании этого феномена ими была предложена процедура построения наглядной модели сети, которой присущ этот феномен. Три состояния этой сети предКонкурентная разведка в компьютерных сетях ставлены на рис. 35: регулярная сеть – каждый узел которой соединен с четырьмя соседними, та же сеть, у которой некоторые «ближние» связи случайным образом заменены «далекими» (именно в этом случае возникает феномен «малых миров») и случайная сеть, в которой количество подобных замен превысило некоторый порог.
В реальности оказалось, что именно те сети, узлы которых имеют одновременно некоторое количество локальных и случайных «далеких» связей, демонстрируют одновременно эффект малого мира и высокий уровень кластеризации.
С концепцией «малых миров» связан также практический подход, называемый «сетевой мобилизацией», которая реализуется над структурой «малых миров». В частности, скорость распространения информации благодаря эффекту «малых миров» в реальных сетях возрастает на порядки по сравнению со случайными сетями, ведь большинство пар узлов реальных сетей соединены короткими путями.
Экспертами по проблемам безопасности эффект «малых миров» в последнее время все чаще связывается с сетями террористических организаций, так называемыми оверлейными сетями, т.е.
сетями, надстроенными поверх сети Интернет.
Анализируя связи в сети, можно узнать о ее важных свойствах, например, выявить наличие кластеров, определить их состав, различия в связности внутри и между кластерами, идентифицировать ключевые элементы, связывающие кластеры между собой и т.д.
Вместе с тем серьезным препятствием при анализе является неполная информация о связях между отдельными узлами сети.
Недавно группа исследователей из Института Санта Фе (Santa Fe Institute) представила алгоритм, с помощью которого становится возможным автоматическое получение информации об иерархической структуре подобных сетей [Clauset, 2008]. Новый метод восстановления связей может поступить на вооружение как спецслужб, так и подразделений конкурентной разведки компаний. Так, например, зная только о половине связей между террористами, можно будет с высокой вероятностью восстановить недостающие звенья всей цепочки.
Даже не имея полного описания системы можно получать репрезентативную выборку связей и по ней пытаться достроить всю сеть. Анализ получающегося графа позволяет выявить потенциально важные связи, которые не удалось обнаружить в реальной сети. Например, имея информацию только о половине контактов участников сети между собой, можно с вероятностью 0,8 прогнозировать те связи, о которых сначала ничего не было известно. Очевидно, что данный метод может быть очень полезным при выявлении скрытых сетевых группировок, и таким образом поставить дело обеспечения государственной и коммерческой безопасности на качественно новый уровень.
Для анализа сложных сетей понятий, упоминаемых в отдельных документах из информационных потоков, могут применяться методы глубинного анализа текстов, а точнее контент-мониторинга и экстрагирования таких понятий, как персоны, компании, топонимы (географические названия) и т.п.
Одним из направлений анализа социальных сетей является визуализация, которая имеет важное значение, поскольку зачастую позволяет делать важные выводы относительно характера взаимодействия субъектов-узлов, не прибегая к точным методам анализа.
При отображении модели сети может оказаться целесообразным:
– размещение узлов сети в двух измерениях;
– пространственное упорядочение объектов в одном измерении в соответствии с некоторыми количественными свойствами;
– использование общих для всех сетевых диаграмм методов для отображения количественных и качественных свойств объектов и отношений.
В качестве примеров визуализации сетей можно рассмотреть некоторые разработки компании TouchGraph. Так, например, система TouchGraph Amazon отражает сеть, порожденную книгами и связями между ними (по тематикам, авторам, издательствам).
Компания TouchGraph также реализовала интерфейс для построения социальной сети на основе Livejournal – TouchGraph LiveJourКонкурентная разведка в компьютерных сетях nal Browser. В случае визуализации WWW средствами TouchGraph SEO Browser (www.touchgraph.com/seo) ребрами выступают не гиперссылки, а отношения подобия.
Сервис TouchGraph SEO Browser представляет собой Javaапплет, позволяющий визуализировать связи подобия между вебсайтами, которые рассчитываются в поисковой системе Google. В этом интерфейсе можно увидеть все веб-сайты, связанные отношением подобия с заданным понятием, при этом пользователь может указывать глубину связей и отображать взаимосвязи различных понятий. TouchGraph SEO Browser – весьма полезный инструмент также при поиске веб-сайтов, связанных с исходным общей тематикой (рис. 36).
Рис. 36 – Фрагмент отображения связей веб-серверов (от TouchGraph) В качестве примера применения возможностей анализа социальных сетей приведем фрагмент исследования сети связей понятий (фамилий персон), экстрагируемых из корпусов неструктурированных текстов – массивов документов, сканируемых из сети Интернет системой контент-мониторинга InfoStream [Григорьев, 2007].
При построении сети понятий использовались алгоритмы автоматического извлечения понятий из неструктурированных текстов. Следует отметить, что подходы к извлечению различных типов понятий из текстов существенно отличаются как по контексту их представления, так и по структурным признакам. Так, для выявления принадлежности документа к рубрике тематического классификатора могут использоваться специальным образом составленные запросы, включающие логические и контекстные операторы, скобки и т.п.
Выявление географических названий предполагает использование таблиц, в которых помимо шаблонов написания этих названий используются коды стран, названия регионов и населенных пунктов.
Еще один вид понятий, такой как «персоны», экстрагируется из текстов на основании правил, учитывающих таблицы допустимых имен и фамилий, шаблоны инициалов, возможные варианты совместного написания инициалов/имен и фамилий.
Следует отметить, что система InfoStream включает средства извлечения понятий и, среди прочего, предоставляет пользователям результаты в виде «информационных портретов», включающих такие понятия, как ключевые слова, географические названия, фамилии персон, названия фирм и т.д. В рамках этой системы анализируются свойства сетей, образованных понятиями, связанных друг с другом упоминаниями в тех же документах.
Сеть, образованная понятиями, извлекаемыми из потоков текстов, не статичен, а зависит от объемов документов, из которых извлекаются соответствующие понятия. Следовательно, для понимания структуры такой сети необходимо учитывать ее эволюцию.
Ребрам исходной сети приписываются весовые значения, равные количеству документов, в которых встречаются упоминания персон, отвечающих узлам. Для предотвращения «шума», ребра с весом, меньше чем 2 не учитывались. При развитии сети с фиксированным количеством персон, при увеличении количества рассмотренных документов среднее расстояние между узлами, соответственно уменьшается, достигая своего логического насыщения.
Интересен тот факт, что узлы рассматриваемой сети персон с максимальным количеством исходящих ребер преимущественно имеют наибольший уровень посредничества и не могут рассматриваться в качестве основы для построения кластеров при автоматической группировке, а скорее как элементы, соединяющие отдельные группы узлов.
Информационная сеть персон (наиболее упоминаемых) и их связей, полученных путем анализа выходного потока по экономической проблематике за определенный период времени, представлена в виде графа (рис. 37).
Конкурентная разведка в компьютерных сетях Рис. 37 – Отображение информационной сети персон Полученные эмпирические результаты могут быть полезными, например, при моделировании экономико-социальных процессов, выявлении и визуализации неявных связей отдельных объектов или субъектов. Феномен стабилизации сети связей на практике позволяет путем анализа небольшого массива документов выявлять устойчивые связи, снижать влияние шумовых факторов. Вместе с тем пока остается открытым вопрос оценки корреляции полученных информационных взаимосвязей персон, рассчитанных путем подсчета частоты документов, в которых персоны упоминаются совместно, и взаимосвязей реальных.
В список крупнейших социальных сетей, которые могут быть интересными для конкурентной разведки, можно включить:
- Facebook;
- ВКонтакте;
- LinkedIn;
- Livejournal;
Facebook (www.facebook.com) – крупнейшая социальная сеть, основанная в 2004 году М. Цукербергом и его компаньонами. Начиная с сентября 2006 года социальная сеть доступна для пользователей сети Интернет. 4 октября 2012 года аудитория Facebook составила 1 миллиард пользователей. Суточная активная аудитория превышает 525 миллионов человек. Около 500 млн. человек в месяц используют мобильные приложения Facebook. Каждый день в социальной сети пользователи оставляют 3,2 миллиарда «лайков»
и комментариев и публикуют 300 миллионов фотографий. На сайте зафиксировано 125 млрд. «дружеских связей». Ежемесячное количество просмотров страниц Facebook превышает 1 триллион.
«ВКонтакте» (vk.com) – крупнейшая в Рунете социальная сеть, созданная П. Дуровым в 2006 г., позиционирующая себя как «современный, быстрый и эстетичный способ общения в сети». По данным на начало 2013 года ежедневная аудитория «ВКонтакте»
составляет более 43 миллионов пользователей. Пользователям «ВКонтакте» доступен характерный для многих социальных сетей набор возможностей: создавать профиль с информацией о себе, производить и распространять контент, управлять настройками доступа, взаимодействовать с другими пользователями приватно и публично, отслеживать через ленту новостей активность друзей и сообществ. Социальная сеть «ВКонтакте» предлагает сторонним ресурсам использовать специально разработанные инструменты – виджеты – для глубокой интеграции с социальной сетью. Эти решения позволяют встраивать в веб-сайты систему комментариев для пользователей, сообщества, системы опросов, а также возможность легко поделиться ссылкой на материал с другими пользователями и авторизоваться на сайте. У сайта имеется мобильная версия, расположенная по адресу m.vk.com. 24 мая 2013 г. Роскомнадзор внёс домен vk.com и его IP-адрес в «Единый реестр запрещённых сайтов», однако уже через несколько часов удалил его оттуда, обосновав ошибку человеческим фактором.
Google+ (plus.google.com) – социальная сеть от компании Google, официально начавшая свою работу в 2011 г. На начало 2012 г.
Конкурентная разведка в компьютерных сетях количество зарегистрированных в Google+ пользователей превышало девяносто миллионов человек. Сервис предоставляет возможность общения через Интернет с помощью специальных компонентов: Круги, Темы, ВидеоВстречи, Мобильная версия. Основополагающими принципами действия сервиса являются пользователи, приватность и живое общение. Информация, которой делятся участники сети, влияет на персонализированные результаты поиска Google. В основе работы Google+ лежит концепция кругов (Circles), благодаря которым пользователь регулирует свое общение. На основе кругов пользователь делится контентом, определяя, какой круг будет иметь доступ к информации, а какой нет. Обмен пользовательскими материалами идёт в специальной ленте (Stream), в которой можно следить за обновлениями участников кругов. Google была представлена также и мобильная версия социальной сети, в которой есть две уникальных функции: мгновенная загрузка фото и Чат (Huddle). Социальная сеть Google+ позволяет получать хорошие позиции в поиске Google.
«Мой Круг» (www.moikrug.ru) – русскоязычная социальная сеть, направленная на установление деловых контактов между людьми. Архитектура сети представляет собой круги пользователей, где первый круг – это близкие друзья пользователя, которым он доверяет свою контактную информацию, второй круг – это друзья друзей пользователя, а третий соответственно друзья друзей его друзей. Сеть «Мой Круг» была создана в 2005 г. В 2007 г. проект был куплен компанией «Яндекс». Теперь он является одним из сервисов Яндекса. В 2009 году к сервису был подключен экспорт вакансий из крупнейших тематических сайтов: hh.ru и rabota.mail.ru. В 2011 году социальная сеть «Мой круг» завершил процесс интеграции с социальными платформами – появилась возможность поиска друзей через аккаунты Facebook, Twitter, LiveJournal и LinkedIn.
LinkedIn (www.linkedin.com) – социальная сеть для поиска и установления деловых контактов. В LinkedIn зарегистрировано свыше 200 миллионов пользователей из 200 стран, представляющих 150 отраслей бизнеса. Социальная сеть LinkedIn, основанная Р.
Хоффманом, была запущена в эксплуатацию в 2003 г. Эта социальная сеть предоставляет возможность зарегистрированным пользователям создавать и поддерживать список деловых контактов. Контакты могут быть приглашены как из сайта, так и извне, однако LinkedIn требует предварительного знакомства с контактами. В случае, когда пользователь не имеет прямой связи с контактом, он может быть представлен через другой контакт. Список контактов LinkedIn может использоваться для: расширения связей, поиска компаний, людей и групп по интересам, публикации резюме и поиска работы рекомендовать пользователей (быть рекомендованными), публиковать вакансии, создавать группы по интересам. Социальная сеть LinkedIn также позволяет публиковать информацию о деловых поездках и конференциях.
Badoo (badoo.com) – социальная сеть знакомств, основанная в 2006 г. российским бизнесменом А. Андреевым. По состоянию на 2013 г. в Badoo зарегистрировано более 180 миллионов пользователей. Зарегистрировавшись, пользователь может общаться в чате, загружать на сайт свои фотографии, связываться с друзьями в своем регионе или за его пределами. Существуют также премиумуслуги, которые являются платными. Они предоставляются тем, кто хочет иметь большую популярность, расширить круг знакомств.
За время своего существования компания Badoo выпустила несколько продуктов под свободной лицензией, включая различные улучшения языка программирования PHP, сервер Pinba, собирающий статистику в реальном времени, бесплатный быстрый шаблонизатор Blitz для PHP.
«Живой Журнал», ЖЖ, LiveJournal, LJ (www.livejournal. com) – платформа для ведения онлайн-дневников (блогов), созданная в 1999 г. американским программистом Б. Фицпатриком.
ЖЖ предоставляет пользователям возможность публиковать свои и комментировать чужие записи, вести коллективные блоги («сообщества»), добавлять в друзья («френдить») других пользователей и следить за их записями в «ленте друзей» («френдленте»). Серверы ЖЖ находятся в США и система принадлежит американской компании LiveJournal, Inc., хотя ей и владеет российская компания SUP Media. По данным статистики LiveJournal.com на конец 2012 г.
в «Живом Журнале» зарегистрировано более 40 млн. пользователей. Среди настроек, функций и опций «Живого Журнала» следует выделить: разные типы записей и возможности их комментирования; указание расширенных сведений о пользователе; друзья и лента друзей; картинки пользователей; функции безопасности аккаунта.
«