Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Համայնքների հայտնաբերման ինֆորմացիոն տեսական հետազոտում և խորհրդատվական միջավայրի մշակում

Մխիթարյան, Կարեն Կառլենի (2019) Համայնքների հայտնաբերման ինֆորմացիոն տեսական հետազոտում և խորհրդատվական միջավայրի մշակում. PhD thesis, ՀՀ ԳԱԱ ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (3649Kb) | Preview

    Abstract

    Վերջին տարիներին տեղեկատվական տեխնոլոգիաների բուռն զարգացումր մասնագետներին տրամադրել է զանգվածային տվյալներ և հաշվարկային բավարար ռեսուրսներ այդ տվյալների մշակման և վերլուծության համար: Զգսւ|իորեն աճել են նաև իրական ցանցերի չափերը հասնելով միլլիոնավոր կամ միլլիարդավոր գագաթների և կողերի: Նման մեծ թվով միավորների հետ աշխատելու անհրաժեշտությունը խորապես փոխել է գրաֆների հետազոտման մոտեցումները: Ցանցը գագաթների հավաքածու է, որոնք միմյանց հետ կապված են տարբեր հատկություններով օժտված կողերով: Բարդ ցանցերը գրաֆների կամ ցանցերի տեսակ են, որոնք օժտված են ոչ տրիվիալ տոպոլոգիական հատկանիշներով, որոնք ի տարբերություն պարզ գրաֆների, հիմնականում հանդիպում են իրական աշխարհի փոխազդեցությունները մոդելավորող ցանցերում: Բարդ ցանցերի օրինակ են սոցիալական, տեխնոլոգիական, տեղեկատվական և կենսաբանական ցանցերը, որոնցում էականորեն նկատվում է ոչ տրիվիալ տոպոլոգիական կառուցվածք' անհամասեռ գագաթային աստիճանների բաշխում, համայնքային և հիերարխիկ կառուցվածք, ինչպես նաև գագաթների միջև ոչ կատարելապես կանոնավոր, ո՛չ ամբողջովին պատահական կապեր: Բարդ ցանցերի ուսումնասիրումը երիտասարդ գիտական ուղղություն է, որի զարգացմանը խթանել են համակարգչային և սոցիալական ցանցերի ուսումնասիրումը: Իրական աշխարհի բարդ ցանցերը պարունակում են գագաթների թաքնված խմբավորումներ համայնթներ. որոնք իրենց համայնքի ներսում ունեն ավելի խիտ փոխազդեցություններ քան ցանցի մնացած այլ համայնքների հետ: Ցանցերում համայնքների ուսումնասիրումը ունի բազմաթիվ կիրառություններ տարբեր ոլորտներում, ինչպիսիք են համակարգչային գիտությունը, մեքենայական ուսուցումը, բժշկությունը, կենսաբանությունը և սոցիոլոգիան: Համայնքների հայտնաբերման նպատակն է ցանցերում գտնել խիտ փոխազդեցություններով օժտված գագաթների խմբավորումներ : Չնայած նրան, որ գրականության մեջ առկա են համայնքների հայտնաբերման բազմաթիվ մոտեցումներ և ալգորիթմներ, դրանց գնահատումը մնում է բարդ խնդիր, քանի որ տարբեր ցանցերի համար ստացվում են տարբեր արդյունքներ: Այդ պատճառով ոլորտում դեռ կան բազմաթիվ բաց խնդիրներ: Որոշ դեպքերում համայնքների հայտնաբերման շատ մոտեցումներ կարող են հաջողել, մինչդեռ այլ դեպքերում ալգորիթմները կարող են ձախողվել հաշվարկային բարդության պատճառով: Այսպիսով, կարևոր խնդիր է ուսումնասիրել այն իրավիճակները, երբ համայնքների հայտնաբերումը կարող է լուծվել արդյունավետորեն կամ ինֆորմացիոն- տեսականորեն: Համայնքների հայտնաբերման ալգորիթմների միջոցով ստացված համայնքային կառուցվածքների գնահատման համար կարևոր է դրանց ուսումնասիրումը տարբեր տեսակի ցանցերի վրա, օգտագործելով համայնքների և համայնքային կառուցվածքների գնահատման և համեմատման ներքին և արտաքին չափեր: Հավանականային ցանցերի մոդելները կամ պատահական գրաֆները կարող են օգտագործվել իրական ցանցերը մոդելավորելու և խնդիրների բարդությունը գնահատելու համար, կամ ստեղծելու ցանցեր' որտեղ իրական համայնքային կառուցվածքը հայտնի է: Վերջինս հնարավորություն է տալիս հասկանալու, թե որքանով է մոդելը համապատասխանում իրական տվյալներին, և շատ կարևոր է համայնքների հայտնաբերման խնդիրներում, քանի որ կիրառության մեջ բավականաչափ քիչ են ցանցերը, որտեղ իրական համայնքային կառուցվածքը հայտնի է: Դա, մասնավորապես, հայտնի մարտահրավեր է մեծ տվյալների խնդիրներում, որտեղ հնարավոր չէ որոշել կլաստերների որակը մեխանիկորեն: Համայնքների հայտնաբերման բարձր արդյունավետությամբ ալգորիթմներ որոնելիս, որոնք կկարողանան հայտնաբերել «ճիշտ» համայնքներ կամ համեմատել տրված համայնքային կառուցվածքը իրական համայնքային կառուցվածքի հետ, օգտագործվում են տարբեր համեմատման չափեր: Այս ոլորտում ինֆորմացիոն տեսական չափերը հիմնարար տեղ են զբաղեցնում և վերջին տարիներին մեծ հետաքրքրություն են առաջացրել իրենց ուժեղ մաթեմատիկական հիմքի և ոչ գծային նմանությունների հայտնաբերման ունակությունների շնորհիվ: Այնուամենայնիվ, ըստ տարբեր հեղինակների պնդումների , հայտնի ինֆորմացիոն տեսական չափերը, ինչպիսիք են օրինակ' նորմավորված փոխադարձ ինֆորմացիան (NN/11) և ինֆորմացիայի փոփոխությունը (VI), հուսալի վարք չեն դրսևորում , քանի որ դրանք կախում ունեն ցանցում գագաթների և համայնքների քանակից: Այդ կոնտեքստում կարևոր է փորձարկել դրանց կատարողականը, հայտնաբերելու այն դեպքերը, երբ ստացվում են սխալ արդյունքներ և առաջարկել առկա չափերի ձևափոխություններ կամ այլընտրանքներ, որոնք կերաշխավորեն ավելի ճշգրիտ համեմատություններ: Համայնքների հայտնաբերման մոտեցումները ներմուծվել են բազմաթիվ այլ գիտական ուղղություններ, որոնցից մեկը խորհրդատվական համակարգերն են: Խորհրդատվական համակարգը ինֆորմացիայի որոնման համակարգի տեսակ է, որը կանխագուշակում է օգտատերերի նախընտրություններն առարկաների վերաբերյալ' նպատակ ունենալով ստեղծել անհատականացված խորհրդատվություններ: Խորհրդատվական համակարգերի օգտագործումը բազմաթիվ ընկերություններին հնարավորություն է տվել ավելացնել եկամուտները, օգտատերերի գոհունակությունը, ինչպես նաև ակտիվացնել անհատականացում և օգտատերերի համար նոր ինֆորմացիայի բացահայտում: Բովանդակության վրա հիմնված և համագործակցային ֆիլտրման մեթոդներն առավել հայտնի մոտեցումներն են խորհրդատվական համակարգերում, որոնք կանխագուշակում են օգտատերերի նախընտրությունները' հիմնվելով համակարգում առկա օգտատերերի և առարկաների միջև համագործակցային տվյալների վրա: Սակայն, առկա խորհրդատվական մոտեցումներն ունեն որոշակի թերություններ, ինչպիսիք են նոսր տվյալների հետ աշխատելու դժվարությունները, մեծածավալ տվյալների դեպքում հաշվողական բարդությունը, որոնք սահմանափակում են դրանց օգտագործումը որոշ կիրառություններում: Այդպիսի դեպքերում համայնքների հայտնաբերման մեթոդների կիրառումը հեռանկարային է, քանի որ դրանց միջոցով հնարավոր է բարելավել խորհրդատվություններ իրականացնելու գործընթացի արդյունավետությունը և խորհրդատվությունների ճշգրտությունը: Ատենախոսության հիմնական նպատակն էր առաջարկել գիտականորեն հիմնավորված մոտեցում համայնքների հայտնաբերման ալգորիթմներին և գնահատման չափերին որոշ կիրառություններում: Այդ նպատակով առաջին խնդիրն էր ուսումնասիրել համայնքների հայտնաբերման առկա մոտեցումները և ալգորիթմները, հետազոտել համայնքների և համայնքային կառուցվածքների գնահատման ներքին և արտաքին առկա չափերը' համեմատելով դրանք տարբեր տեսակի փոքր և մեծ իրական բարդ և արհեստականորեն ստացված ցանցերի օգտագործմամբ: Հաջորդ խնդիրն էր առաջարկել նոր մոտեցումներ համայնքների հայտնաբերման ալգորիթմների համեմատման և օգտագործման համար որոշ կիրառություններում: Վերջապես խնդիր էր դրվել ուսումնասիրել համայնքների հայտնաբերման և խորհրդատվական համակարգերի հնարավոր վտխկապակցվածությունը, նպատակ հետապնդելով առաջարկել ավելի արդյունավետ խորհրդատվական մոտեցումներ: Ատենախոսության մեջ հետազոտվել են բարդ ցանցերը, պատահական գրաֆների մոդելները, համայնքների հայտնաբերման հիմնական ալգորիթմները, համայնքների և համայնքային կառուցվածքների գնահատման և համեմատման ներքին և արտաքին չափերը և ինֆորմացիոն տեսական չափերը: Ոսումնասիրվել է նաև համայնքների հայտնաբերման մոտեցումների ներառումը խորհրդատվական համակարգերի որոշ կիրառություններում: Ատենախոսության շրջանակներում կիրառվել են հավանականությունների տեսության, ինֆորմացիայի տեսության, ցանցերի տեսության և կլաստերային վերլուծության հիմնարար մեթոդները: Փորձարարական հետազոտությունների համար օգտագործվել են R և Python ծրագրավորման լեզուները և դրանց' ցանցերի հետազոտության և կլաստերային վերլուծության համար նախատեսված գրադարանները: Խոշոր ցանցերում հաշվոդական մեծ բարդություն պահանջող հետազոտությունների համար օգտագործվել է «OSIRIM» գերհամակարգիչը (http://osirim.irit.fr/site/>: Առաջարկվել ԷՀ - տարամիտության վրա հիմնված նոր ինֆորմացիոն տեսական չափ համայնքային կառուցվածքների համեմատման համար, որը գրականության մեջ առկա չափերի համեմատ ունի առավելություն: հասկանալու, թե ինչպես են աշխատում ալգորիթմները, և որ ալգորիթմն է գերադասելի В последнее время компьютерная революция предоставила специалистам огромные данные и достаточные вычислительные ресурсы для обработки и анализа этих данных. Размер реальных сетей также значительно вырос, достигнув миллионов или даже миллиардов вершин и ребер. Изучение сложных сетей является молодой областью научных исследований, в значительной степени стимулируемой изучением сетей реального мира, таких как компьютерные сети и социальные сети. Сложные сети реального мира обладают скрытой информацией, называемой сообществами или кластерами, которые состоят из узлов, тесно связанных внутри сообществ и слабо связанных между сообществами. Исследования сообществ имеют множество применений в различных науках, таких как информатика и машинное обучение, медицина и биология, экономика и социология. Цель обнаружения сообщества - разделить сеть на сообщества, чтобы извлечь из этой группы подгруппы плотно связанных узлов. Основная цель диссертации состояла в том, чтобы предложить научно обоснованный подход к алгоритмам обнаружения сообщества и оценочным мерам в определенных приложениях. Для этой цели первая задача состояла в том, чтобы исследовать методы и алгоритмы, которые были разработаны для обнаружения сообщества, изучить существующие внутренние и внешние меры оценки обнаружения сообщества, сравнить их на различных типах сетей, как в реальном мире сложных, так и синтетических. Следующая задача состояла в том, чтобы предложить прогресс в области сравнения алгоритмов обнаружения сообщества. Последняя задача состояла в том, чтобы изучить возможные взаимосвязи обнаружения сообществ и рекомендательных систем, преследуя цель предложить сравнительно лучшие подходы для рекомендаций. Основные результаты работы: Исследованы и научно обоснованы связи между проблемами обнаружения сообщества и информационно теоретическими инструментами [1]. Алгоритмы обнаружения сообщества были оценены и сравнены как на небольших, так и крупных реальных сложных сетях и синтетических сетях, сгенерированных из стохастической блочной модели с использованием различных внутренних и внешних метрик для оценки сообщества. Результаты показывают детальную картину того, как алгоритмы работают в сетях с различными свойствами, которые полезны для нахождения подходящего алгоритма для данной сети [2, 3]. Информационно-теоретические меры для сравнения структур сообществ были протестированы на основе трех основных свойств; метрика, нормализация и постоянное базовое свойство. Кроме того, рассмотрено применение Т-дивергенций из теории информации для оценки обнаружения сообществ. В результате предложена модифицированная /2-дивергенция, которая по сравнению с существующими информационно-теоретическими мерами имеет преимущество [4, 5]. Предложена новая рекомендательная среда, которая включает методы обнаружения сообщества в процесс принятия решений. Среда дает In recent times, the computer revolution has provided specialists with massive data and sufficient computational resources to process and analyze these data. The size of real networks has also grown considerably, reaching millions or even billions of vertices and edges. The need to deal with such a large number of units has produced a deep change in the way graphs are approached. The study of complex networks is a young area of scientific research stimulated largely by the study of real world networks like computer networks and social networks. Real world complex networks possess hidden information called communities or clusters, which are composed of nodes that are tightly connected within communities and weakly connected between communities. Investigation of communities proved to have countless applications in different sciences such as computer science and machine learning, medicine and biology, economics and sociology. The goal of community detection is to partition a network into communities to extract the subgroups of densely connected nodes from this network. The main purpose of the dissertation was to suggest scientifically grounded approach for community detection algorithms and evaluation measures in certain applications. For this aim the first task was to investigate the methods and algorithms that have been developed for community detection, to study existing internal and external community detection evaluation measures, to compare them on different types of networks, both real world complex and synthetic. The next task was to propose an advance in the way of comparison of community detection algorithms. The final task was to study the possible interconnections of community detection and recommender systems pursuing an aim to suggest comparatively better recommendation approaches. The main results of the work are the following: Connections between community detection problems and information theoretical tools are investigated and scientifically substantiated [1]. Community detection algorithms were evaluated and compared on both small and large scale real world complex networks and synthetic networks generated from stochastic block model using various internal and external metrics for community evaluation. Results exhibit detailed picture on how algorithms work on networks with different properties that are useful to filter out an appropriate algorithm for a given network [2, 3]. Information-theoretic measures for comparing network partitions or community structures were tested based on three main properties; metric, normalization and constant baseline properties. Additionally the application of /-divergences from information theory in community detection evaluation was observed. As a result, a modified /2-divergence is suggested that compared with existing information- theoretic measures has an advantage [4, 5]. is proposed that incorporates community detection techniques into decision making. The framework gives ability to make recommendations in certain applications where other recommender approaches fail. Its realization is also presented [6, 7]. A deep comparison of state-of-the-art community detection algorithms using both large scale real world complex networks and artificial networks generated from stochastic block model is reported. Internal evaluation measures to assess the quality of community structure and external evaluation measures to compare partitions are applied. These results are very important to understand how particular algorithm works and which algorithm would be preferable in certain scenario. In the context of recommender systems, the newly proposed framework designed with the incorporation of community detection techniques, can be employed in many real life applications where other recommendation approaches are useless. The realization of the platform can be used for various applications.

    Item Type: Thesis (PhD)
    Additional Information: Информационно теоретическое исследование обнаружения сообществ и разработка рекомендательной среды. Information-theoretic investigation of community detection and recommender framework development.
    Uncontrolled Keywords: Мхитарян Карен Карленович,
    Subjects: Control, Automation and Electrical Engineering
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 16 Oct 2019 14:14
    Last Modified: 27 Feb 2020 10:03
    URI: http://etd.asj-oa.am/id/eprint/10717

    Actions (login required)

    View Item