Күш заңына бағынған желілер және масштабсыздық қасиеті

Кіріспе

Күш заңы бойынша дәрежелік таралымына ие желі

Скаласыз желі – бұл, кем дегенде асимптотикалық түрде, дәрежелік таралымы күш заңына сәйкес келетін желі. Яғни, желідегі k байланысы бар түйіндердің үлесі P(k), k-ның үлкен мәндері үшін былай өрнектеледі:

мұндағы – бұл параметр, оның мәні әдетте (2-ден үлкен) диапазонда болады (оның екінші моменті (масштаб параметрі) шексіз, бірақ бірінші моменті шекті), дегенмен кейде бұл шектерден тыс болуы мүмкін. "Скаласыз" атауы дәрежелік таралымның кейбір моменттері анықталмағандығымен түсіндіріледі, сондықтан желіде ерекше масштаб немесе "өлшем" болмайды. Көптеген желілер скаласыз деп хабарланған, бірақ статистикалық талдау осы мәлімдемелердің көпшілігін жоққа шығарды және қалғандарын күмәнді етіп қарады. Сонымен қатар, кейбіреулер дәрежелік таралымның "құйрығының қалыңдығын" білу, желінің статистикалық тұрғыдан нақты анықтамалар бойынша скаласыз екенін білуден маңыздырақ деп санайды. Преференциалдық қосылу және жарамдылық моделі, нақты желілердегі күш заңы бойынша күтілетін дәрежелік таралымды түсіндіруге арналған механизмдер ретінде ұсынылған. Суперсызықтық преференциалдық қосылу және екінші көрші преференциалдық қосылу сияқты балама модельдер уақытша скаласыз желілерді құруы мүмкін, бірақ желілердің мөлшері артқан сайын дәрежелік таралым күш заңынан ауытқиды.

Тарих

Дерек де Солла Прайс ғылыми мақалалар арасындағы цитаталар желілерін зерттеуде 1965 жылы мақалаларға сілтемелердің санының, яғни олар алған цитаталар санының, Парето таралымы немесе қуат заңына сәйкес қатты таралғанын көрсетті, сондықтан цитаталар желісі масштабсыз. Алайда ол бірнеше онжылдықтан кейін ғана пайда болған "масштабсыз желі" терминін қолданған жоқ. 1976 жылы шыққан кейінгі мақаласында Прайс цитаталау желілерінде қуат заңдарының пайда болуын түсіндіру механизмін ұсынды, оны ол "жинақталған артықшылық" деп атады, бірақ ол бүгінде артықшылықты қосылу атауымен кеңірек танымал. Соңғы кездегі масштабсыз желілерге қызығушылық 1999 жылы Нотр-Дам университетіндегі Альберт Ласло Барабаси мен Река Альберттің жұмысымен басталды, олар World Wide Web-тің бір бөлігінің топологиясын картаға түсірді, олар "хабтар" деп атаған кейбір түйіндердің басқаларға қарағанда көбірек байланыстары бар екенін және тұтастай алғанда желіде түйінге қосылатын сілтемелер санының қуат заңдары таралуы бар екенін анықтады. Кейбір әлеуметтік және биологиялық желілерді қоса алғанда, басқа бірнеше желілерде де ауыр құйрықты дәреже үлестірулері бар екенін анықтағаннан кейін, Барабси мен Река Альберт "масштабсыз желі" терминімен қуат заңдарының дәрежесін үлестіретін желілер класын сипаттады. Алайда, әлеуметтік, экономикалық, технологиялық, биологиялық және физикалық жүйелердегі желілердің жеті мысалын зерттей отырып, Amaral және т.б. жеті мысалдың арасында масштабсыз желі таба алмады. Осы мысалдардың тек біреуі, кино актерлер желісі, орташа k үшін қуат заң режимінен кейін P(k) дәрежесін үлестірді, бірақ ақыр соңында бұл қуат заң режимі үлкен k үшін экспоненциалдық ыдырауды көрсететін өткір кесумен ұштасты. Барабаси мен Река Альберт қуат заңдарының таралуын түсіндіру үшін генеративтік механизм ұсынды, оны олар "артықшылықты қосылу" деп атады және ол негізінен Прайс ұсынғанмен бірдей. Бұл механизмнің аналитикалық шешімдерін (Прайс шешімдеріне ұқсас) 2000 жылы Дороговцев, Мендес және Самухин және тәуелсіз түрде Крапивский, Реднер және Лейвраз ұсынды, ал кейін математик Бела Боллобас қатаң дәлелдеді. Алайда, бұл механизм тек масштабсыз кластағы желілердің нақты бір кіші жиынтығын ғана шығарады және содан бері көптеген баламалы механизмдер ашылды. Масштабсыз желілердің тарихында кейбір келіспеушіліктер де бар. Эмпирикалық деңгейде бірнеше желілердің масштабсыз табиғаты күмән тудырады. Мысалы, үш ағайынды Фалуцос Интернет трассоуте деректері негізінде қуат заңдарының дәрежесін бөледі деп сенді; дегенмен, бұл маршрутизаторлар жасаған 3-қабаттық иллюзия, олар жоғары деңгейдегі түйіндер ретінде көрінеді, ал өзара байланысты AS-тің ішкі 2-қабаттық құрылымын жасырады. Теориялық деңгейде масштабсыз абстрактілік анықтаманың жетілдірілуі ұсынылды. Мысалы, Li және басқалар. (2005) "салмақсыз метрика" дегенді ұсынды. Қысқаша айтқанда, G - шеттік жиынтығы E бар график болсын және ұшының дәрежесін (яғни, шектердің саны) белгілеңіз. Бұл жоғары дәрежелі түйіндер басқа жоғары дәрежелі түйіндерге қосылғанда максималдық болады. Енді анықтаңыз, мұнда smax - бұл s(H) үшін H-дің барлық графиктер жиынтығында G-мен бірдей градус үлестірімі бар. Бұл 0 мен 1 арасындағы метриканы береді, мұнда G графигі кішкентай S(G) - "меңгей бай", ал G графигі S(G)-мен 1-ге жақын "меңгейсіз". Бұл анықтама "масштабсыз" деген атаумен түсіндірілген өзіндік ұқсастық ұғымын қамтиды.

In studies of the networks of citations between scientific papers, Derek de Solla Price showed in 1965 that the number of links to papers—i. e., the number of citations they receive—had a heavy tailed distribution following a Pareto distribution or power law, and thus that the citation network is scale free. He did not however use the term "scale free network", which was not coined until some decades later. In a later paper in 1976, Price also proposed a mechanism to explain the occurrence of power laws in citation networks, which he called "cumulative advantage" but which is today more commonly known under the name preferential attachment. Recent interest in scale free networks started in 1999 with work by Albert László Barabási and Réka Albert at the University of Notre Dame who mapped the topology of a portion of the World Wide Web, finding that some nodes, which they called "hubs", had many more connections than others and that the network as a whole had a power law distribution of the number of links connecting to a node. After finding that a few other networks, including some social and biological networks, also had heavy tailed degree distributions, Barabási and Réka Albert coined the term "scale free network" to describe the class of networks that exhibit a power law degree distribution. However, studying seven examples of networks in social, economic, technological, biological, and physical systems, Amaral et al. were not able to find a scale free network among these seven examples. Only one of these examples, the movie actor network, had degree distribution P(k) following a power law regime for moderate k, though eventually this power law regime was followed by a sharp cutoff showing exponential decay for large k.

Barabási and Réka Albert proposed a generative mechanism to explain the appearance of power law distributions, which they called "preferential attachment" and which is essentially the same as that proposed by Price. Analytic solutions for this mechanism (also similar to the solution of Price) were presented in 2000 by Dorogovtsev, Mendes and Samukhin and independently by Krapivsky, Redner, and Leyvraz, and later rigorously proved by mathematician Béla Bollobás. Notably, however, this mechanism only produces a specific subset of networks in the scale free class, and many alternative mechanisms have been discovered since. The history of scale free networks also includes some disagreement. On an empirical level, the scale free nature of several networks has been called into question. For instance, the three brothers Faloutsos believed that the Internet had a power law degree distribution on the basis of traceroute data; however, it has been suggested that this is a layer 3 illusion created by routers, which appear as high degree nodes while concealing the internal layer 2 structure of the ASes they interconnect. On a theoretical level, refinements to the abstract definition of scale free have been proposed. For example, Li et al. (2005) offered a potentially more precise "scale free metric". Briefly, let G be a graph with edge set E, and denote the degree of a vertex (that is, the number of edges incident to ) by Define

This is maximized when high degree nodes are connected to other high degree nodes. Now define

where smax is the maximum value of s(H) for H in the set of all graphs with degree distribution identical to that of G. This gives a metric between 0 and 1, where a graph G with small S(G) is "scale rich", and a graph G with S(G) close to 1 is "scale free". This definition captures the notion of self similarity implied in the name "scale free".

Шолу

"Шағындылықсыз" ұғымы желілер контекстінде алғаш енгізілген кезде, ол басты назарда белгілі бір қасиетке – берілген айнымалы үшін қуат заңының таралуына, яғни ретінде көрсетілгеніне аударды. Бұл қасиет үздіксіз масштабтау түрлендірілген кезде өз түрін сақтайды, бұл статистикалық өріс теориясындағы қайта нормалау тобы әдістерін еске түсіреді. Дегенмен, маңызды айырмашылық бар. Статистикалық өріс теориясында "масштаб" көбінесе жүйе өлшемімен байланысты. Ал желілерде "масштаб" – байланыстылықтың өлшемі, әдетте түйіннің дәрежесі арқылы анықталады, яғни оған қосылған байланыстардың саны. Жоғары дәрежелі түйіндердің саны көп желілер жоғары байланысты деп есептеледі. Қуат заңының дәрежелік таралуы бізге жоғары дәрежелі түйіндердің кең таралғандығы туралы "шағындылықсыз" тұжырымдар жасауға мүмкіндік береді. Мысалы, "орташа байланыстылығы үш есе жоғары түйіндер, орташа байланыстылығы бар түйіндерге қарағанда екі есе сирек кездеседі" деуге болады. "Орташа байланыстылық" сандық мәнінің қандай екені маңызды емес, ол жүз болсын не миллион болсын.

Сипаттамалары

Өлшемсіз желілердің ең ерекше қасиеті – орташа көрсеткіштен әлдеқайда артық дәрежеге ие түйіндердің жиі кездесуі. Ең жоғары дәрежелі түйіндер көбінесе "хабтар" деп аталады, және олар өз желілерінде нақты мақсаттарға қызмет етеді деп саналады, бірақ бұл салаға байланысты.

Кластерлеу

Масштабсыз желілердің тағы бір маңызды ерекшелігі – кластерлеу коэффициентінің таралуы, ол түйіннің дәрежесі артаған сайын төмендейді. Бұл таралым да қуат заңына бағынады. Бұл төмен дәрежелі түйіндердің өте тығыз кішіграфтарға жататынын және осы кішіграфтар хабтар арқылы бір-бірімен байланысқан екенін көрсетеді. Мысалы, әлеуметтік желіде түйіндер адамдар, ал байланыстар – адамдар арасындағы таныстық қатынастар. Адамдардың қауымдастықтар, яғни әркімнің әркімді танитын шағын топтар құрайтынын байқау оңай (мұндай қауымдастықты толық граф ретінде қарастыруға болады). Сонымен қатар, қауымдастықтың мүшелері сол қауымдастықтан тыс адамдармен де бірнеше таныстық байланысқа ие болады. Дегенмен, кейбір адамдар көптеген қауымдастықтармен байланысты болады (мысалы, атақты адамдар, саясаткерлер). Осы адамдар шағын әлем құбылысына жауапты хабтар деп есептелуі мүмкін. Қазіргі уақытта масштабсыз желілердің нақты сипаттамалары оларды жасау үшін қолданылатын генерациялық механизмге байланысты өзгереді. Мысалы, басымдықпен қосылу арқылы құрылған желілерде жоғары дәрежелі түйіндер әдетте желінің ортасына орналасады, оларды ядроны құру үшін біріктіреді, ал ядро мен шеткері аймақтарды төмен дәрежелі түйіндер құрайды. Тіпті көптеген түйіндерді кездейсоқ жою желінің жалпы байланыстылығына аз ғана әсер етеді, бұл мұндай топологиялар қауіпсіздік үшін пайдалы екенін көрсетеді, ал бағытталған шабуылдар байланысты тез жояды. Жоғары дәрежелі түйіндерді шеткері аймаққа орналастыратын басқа масштабсыз желілер мұндай қасиеттерді көрсетпейді. Сол сияқты, масштабсыз желілердің кластерлеу коэффициенті де басқа топологиялық ерекшеліктерге байланысты айтарлықтай өзгеруі мүмкін.

Иммундау

Интернет пен әлеуметтік желілер сияқты нақты желілерді бейнелейтін масштабсыз желілерді тиімді иммундау мәселесі жан-жақты зерттелді. Мұндай стратегиялардың бірі – ең жоғары дәрежелі түйіндерді иммундау, яғни мақсатты (ішінен таңдалған) шабуылдар, себебі осы жағдайда p салыстырмалы түрде жоғары және иммундау үшін аз түйіндер қажет. Дегенмен, көптеген нақты жағдайларда жаһандық құрылым қолжетімді болмайды және ең жоғары дәрежелі түйіндер белгісіз болады. Кездейсоқ графтардың қасиеттері графтарды түрлендіру кезінде өзгермей немесе сақталуы мүмкін. Мысалы, Mashaghi A. және авторлар тобы кездейсоқ графтарды олардың жиектерінің дуалдық графтарына (немесе сызықтық графтарына) түрлендіретін трансформация, шамамен бірдей дәрежелік таралымға, бірақ дәрежелік корреляцияларға және едәуір жоғары кластерлеу коэффициентіне ие графтар жиынтығын тудыратынын көрсетті. Масштабсыз графтар осындай түрлендірулер кезінде масштабсыз күйінде қалады.

Жалпыланған масштабсыз модель

Масштабсыз күрделі желілерді модельдеуде қызу қызмет басталып келеді. Барабáси мен Альберт ұсынған әдіс бірнеше өзгерістер мен жалпылауларға ұшырады, сондай-ақ бұрынғы математикалық еңбектер жаңарып, қайта қарастырылды. Қазіргі терминологияда, егер күрделі желінің кез келген көрсеткішінің таралуы қуат заңына бағынса, онда ол масштабсыз желі деп есептеледі. Сол сияқты, осы қасиетке ие кез келген модель масштабсыз модель деп аталады.

Гиперболалық геометриялық графиктер

Егер желінің негізінде гиперболалық геометрия болса, масштабсыз дәреже таралуын жасау үшін кеңістіктік желілердің аясын қолдануға болады. Бұл әртүрлі дәреже таралуы гиперболалық геометрияның теріс қисықтығы мен метрикалық қасиеттерін ғана көрсетеді.

Қажетті қасиеттері бар масштабсыз графиктерді құру үшін жиектік қос түрлендіру

Кемелсіз графиктерден бастап, төмен дәрежелі корреляция және кластерлеу коэффициентіне ие графиктерге, шеттік дуалды түрлендіруді қолдану арқылы әлдеқайда жоғары дәрежелі корреляция және кластерлеу коэффициенттері бар жаңа графиктер жасауға болады. Өлшемінен бос идеалдық желілер модельдерінде Дунбар санының "алты қол аралық қашықтық" деп аталатын құбылыстың себебі екенін көрсету мүмкін.

Жаңа сипаттамалары

Түйіндері мен қуат заңы көрсеткіші бар масштабсыз желіде, дәрежесінен үлкен түйіндерден құралған шақырылған кіші желі, дерлік сөзсіз, көрсеткіші бар масштабсыз желі болып табылады.

Қуат заңдарының экспонентін бағалау

Масштабсыз желідегі қуат заңының көрсеткішін бағалау әдетте бірнеше біркелкі таңдалған түйіндердің дәрежелерін қолдана отырып, ең жоғары ықтималдықпен бағалау арқылы жүзеге асырылады. Теориялық тұрғыдан алғанда, кездейсоқ байланыстарды қолдана отырып ең жоғары ықтималдықпен бағалау, біркелкі таңдауға негізделген классикалық тәсілге қарағанда кішірек бұрмалану мен кішірек дисперсияға алып келеді.