1. Цели и задачи

Объектом исследования в работе является интеграция фотогалерей профилей пользователей. Предметом исследования является алгоритм для объедения фотогалерей профилей пользователей из связанных подгрупп социальных сетей.

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

2. Актуальность темы

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

3.1 Социальный граф

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

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

Рисунок 3.1 – Граф взаимодействий исторических личностей

Связи графа могут быть направленными или ненаправленными. Отношения вроде товарищества или соседства формируют граф с ненаправленными связями (рис. 3.2). Вариант графа с направленными связями показан на рис. 3.3. Данный граф построен по ответам на вопрос «С кем бы вы хотели дружить?», заданный коллективу из четырех человек.

Рисунок 3.2 – Граф с ненаправленными связями

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

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

Например, путь от а до d (см. рис. 3.2) – это вершина а, ребро аb, ребро bd и вершина d.

Или вершина а, ребро ас, ребро сd и вершина d.

Расстояние между вершинами – это количество шагов, которые нужно сделать, чтобы добраться от одной вершины до другой, то есть на рис. 1.2 расстояние от a до b равно 1, а от а до d — 2.

Вершины в графе могут быть связаны разными способами:

• напрямую, если между вершинами есть ребро или дуга — так, например, на социограмме (рис. 3.3) связаны Ваня и Аня;
• косвенно, если между ними существует путь, например Ваня и Петя;
• с помощью базовой связи, когда вершины связаны напрямую и никак иначе.

Рисунок 3.3 – Граф с направленными связями

В анализе социальных сетей на базе теории графов выделяют:

• расчет индексов для социальной сети в целом;
• для отдельных агентов сети;
• выделение подструктур в социальной сети.

Для расчета индексов для социальной сети в целом используют элементарные параметры, такие как число вершин или ребер, и некоторые вычисляемые параметры. Например, плотность вычисляется как нормированное число ребер – отношение наличных связей в сети к возможному максимальному количеству связей в сети с данным количеством вершин. Число симметричных диад (на рис. 3.3 таких диад две: Ваня – Катя и Катя – Петя) является показателем стабильности социальной сети. Количество транзитивных триад (рис. 3.4) и циклических триад тоже позволяет оценивать стабильность сети.

Рисунок 3.4 – Граф транзитивных триад

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

Структурные дыры (structural holes) — вид структуры сети, при котором интересующий нас агент сети связан с некоторым числом других агентов, которые не связаны между собой. Если между агентами сети есть социальная дыра, это значит, что они не имеют возможности взаимодействовать напрямую. Таким образом, агенты сети, соединяющие несвязанных агентов, получают возможность выступать посредниками и контролировать их взаимодействие.

При расчете индексов для отдельных вершин выделяют следующие параметры:

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

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

Существует несколько подходов к выделению подструктур в социальной сети:

• определение клик в социальной сети. Клики — это подгруппы, в которых агенты связаны между собой сильнее, чем с членами других клик;
• выделение компонентов (частей графа), которые связаны внутри и не связаны между собой. Если в социальной сети есть один или несколько изолированных членов, то они являются компонентами;
• нахождение блоков и перемычек. Вершина называется перемычкой (cutpoint), если при ее удалении граф распадается на блоки (несвязанные части социальной сети);
• выделение группировок (factions) — групп эквивалентных агентов сети, которые имеют максимально похожие профили связей [1].

3.2 Технология OpenCV

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

OpenCV – библиотека компьютерного зрения с открытым исходным кодом, доступная для загрузки. Библиотека написана на C и C++, работает под Linux, Windows и Mac OS X. Происходит активная разработка интерфейсов для Python, Ruby, MATLAB и других языков.

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

В целом OpenCV предоставляет инструментарий, достаточный для решения подавляющего большинства задач компьютерного зрения. Если алгоритм не имеется в составе SDK, то, как правило, он может быть без проблем запрограммирован. Кроме того, существует множество авторских версий алгоритмов, написанных пользователями на основе OpenCV.

Также следует отметить, что за последние годы OpenCV сильно расширилась и стала в некоторой степени «тяжеловесной». В связи с этим, разными группами энтузиастов создаются «облегченные» библиотеки, основанные на OpenCV [2].

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

3.3 Геотегинг

Геотегинг – процесс присоединения географических метаданных к различным информационным ресурсам, таким как веб-сайты, RSS, фотографии, как-либо характеризующие эти ресурсы (точка съемки, месторасположение и т. п.). Эта информация состоит, как правило, из координат широты и долготы, хотя она может включать также высоту, расстояние и направление до населенных пунктов. Первым шагом в процессе геотегинга является сопоставление географических мест с соответствующими снимками. Есть два способа проделать эту операцию: автоматический и ручной.

Для автоматической записи GPS-координат места съёмки в EXIF-данные используется фотокамера, оснащённая встроенным GPS-приёмником, записывающая координаты в файл непосредственно в момент создания снимка.

Введение точных координат прямо в программе можно назвать ручным способом. В этом случае с помощью специальных программ вручную модифицируют GPS-секцию в EXIF-данных фотографии [3].

4. Алгоритм интеграции фотогалерей профилей пользователей

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

Алгоритм интеграции фотогалерей представлен на рисунке 4.1

Рисунок 4.1 – Алгоритм интеграции фотогалерей
(анимация: 6 кадров, 10 циклов повторения, 185 килобайт)

Выводы

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

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

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2014 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

1. Социальные сети и интернет.[Электронный ресурс]/ А. Прохоров. – Режим доступа: http://www.compress.ru/article.aspx?id=16723&iid=776
2. Что такое OpenCV. Электронный ресурс. Режим доступа: http://locv.ru/wiki/1.1_%D0%A7%D1%82%D0%BE_%D1%82%D0%B0%D0%BA%D0%BE%D0%B5_OpenCV
3. Геотегинг. Материал из Википедии – свободной энциклопедии. Электронный ресурс. Режим доступа:http://ru.wikipedia.org/wiki/Геотегинг
4. Feld, Scott L. (1981). The Focused Organization of Social. American Journal of Sociology. 86(5). 1015-1035
5. Ferligoj, Anuska and Valentina Hlebec. (1999). Evaluation of Social Network Measurement Instruments. Social Networks. 21. 111-130.
6. Fu, Yang-chih. (2005). Measuring Personal Networks with Daily Contacts: A Single-Item Survey Question and the Contact Diary. Social Networks. 27. 169-186.
7. Golder, Scott A. and Bernardo A. Huberman. (2006). Usage Patterns of Collaborative Tagging Systems. Journal of Information Science. 32(2) 198-208.
8. Granovetter, Mark S. (1974). Getting a Job: A Study of Contacts and Careers. Cambridge, MA: Harvard U. P.
9. Higgins, Christopher A., Ronald J. McClean and David W. Conrath. (1985). The Accuracy and Biases of Diary Communication Data. Social Networks. 7. 173-187.
10. Kindberg, Tim, Mirijana Spasojevic, Rowanne Fleck and Abigail Sellen. (2005). An In-Depth Study of Camera Phone Use. IEEE Pervasive Computing. April-June 2005. 42-50.
11. Milgram, Stanley. (1967). The Small World Problem. Psychology Today. Vol. 1, issue 61.
12. Rodden, Kerry, and Kenneth R. Wood. (2003). How do People Manage their Digital Photographs? Proc. CHI 2003.
13. Tyler, Josh, Dennis Wilkinson & Bernardo A. Huberman. (2003). Email as Spectroscopy: Automated Discovery of Community Structure within Organizations. Communities and Technologies 2003.
14. Viegas, Fernanda B., Scott Golder & Judith S. Donath. (2006). Visualizing Email Content: Portraying Relationships from Conversational Histories. Proc. CHI 2006.
15. Wasserman, Stanley and Katherine Faust. (1994). Social Network Analysis: Methods and Applications. Cambridge.
16. Wu, Fang and Bernardo A. Huberman. (2004). "Finding Communities in Linear Time: A Physics Approach." Eur. Phys. J. 38(2). Springer.