Презентация на тему «Некоторые известные структурные модели»

Некоторые известные структурные модели

Модель «галстук-бабочка» (модель Бродера)

Bow tie model of the Web [A. Broder, R. Kumar, F. Maghoul1, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener Graph structure in the web // Journal of Computer Networks. – 2000. ? № 33(1-6). – Р. 309-320]. С использованием AltaVista исследовано несколько миллиардов исходящих ссылок с ~200 миллионов веб-страниц.

(1) центральное ядро (SCC, 30% веб-страниц); (2) входные веб-страницы (IN, 23,3% веб-страниц); (3) оконечные веб-страницы (OUT, 23,3% веб-страниц) – страницы, к которым можно прийти по ссылкам из ядра, но нельзя вернуться назад (правое крыло бабочки); (4) «отростки» и «перешейки» (T&D, 23,3% веб-страниц).

Почему часто изучаются фрагменты Веба

~300 сайтов - академический фрагмент Веба

Модель «короны» (‘corona’ graph model)

7669 UK university sub-sites, Lennart Bj?rneborn, 2004

Фрагменты Веба

German network of university web domains (110 nodes; arcs weight? 50).

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

Структурные исследования фрагментов Веба (группа по вебометрике ИПМИ

КарНЦ РАН webometrics.krc.karelia.ru)

Кусочек образовательного Веба Санкт-Петербурга

Определение 1. Веб-сайт (сайт) – совокупность html-страниц и

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

Определение 2. Прямая внешняя гиперссылка с сайта s на сайт t ? это кортеж <s, source_s, level, context, t, target_t>, где: s, t – доменные имена сайтов, source_s – адрес страницы сайта s, на котором размещена гиперссылка (страница-источник, или исходная страница), .....

Определение 3. Уникальной прямой внешней гиперссылкой называется гиперссылка из множества всех гиперссылок, имеющих одинаковый контекст и адрес целевой страницы, сделанная с исходной страницы с наивысшим уровнем; если на наивысшем уровне таких ссылок несколько, то выбирается любая из них.

<a href=http://petrsu.karelia.ru/index.html>Petrozavodsk State University</a>

Почему нужен свой краулер

Просто Google – мы уже знаем SocSciBot - http://socscibot.wlv.ac.uk/ Webometric Analyst - http://lexiurl.wlv.ac.uk/

Описание структуры BeeBot

BeeCrawler

BeeKeeper

BeeGraph

Концептуальная модель фрагмента Веба для регламентируемого

тематического целевого множества: KM={T, B, K, S, Att, Char}, T – целевое множество, B – множество сайтов ближайших окрестностей, K – множество сайтов-коммуникаторов, S – множество сайтов оболочки, Att – множество отношений, определяющих структуру KM; Char – множество атрибутов объектов KM. Ближайшей окрестностью Bt веб-сайта t?T называется множество сайтов его организации-владельца, являющихся элементами U, на которые существуют гиперссылки с официального сайта, .

Концептуальная модель фрагмента Веба

Веб-коммуникатором называется сайт, принадлежащий U и имеющий входящие

ссылки с «достаточно большого» количества сайтов T и/или исходящие ссылки на «достаточно большое» количество сайтов из T. insitecount(A,s) – количество сайтов из множества А, имеющих гиперссылки на заданный сайт s, outsitecount(s, A) – количество сайтов из А, на которые существуют гиперссылки с сайта s.

T_genre – функция тематической близости сайта u?u к тематике целевого множества T , t_genre(u)=1, если сайт u тематически близок к T , иначе t_genre(u)=0.

- Нижнее пороговое значение: ? - верхнее пороговое значение:

Тематическим сайтом-посредником называется сайт u

U\B, для которого выполняется условия insitecount(T,u)??&outsitecount(u,T)?? и T_genre(u)=1. Множество тематических сайтов-посредников обозначим K?. Тематическим сайтом-коллектором называется сайт u?U\B, для которого выполняется условие insitecount(T,u)??&?>outsitecount(u,T)?1 и T_genre(u)=1. Множество тематических сайтов-коллекторов обозначим K?. Тематическим сайтом-индуктором называется сайт u?U\B, для которого выполняется условие ?>insitecount(T,u)??&outsitecount(u,T)?? и T_genre(u)=1. Множество тематических сайтов-индукторов обозначим K?. Сайты-посредники, коллекторы и индукторы, для которых T_genre(u)=0, составляют множество KOther («нетематические» веб-коммуникаторы). Множество веб-коммуникаторов – это K=K??K??K??KOther.

Множество сайтов оболочки S=U\(B

K) составляют сайты из U, не являющиеся сайтами ближайших окрестностей или веб-коммуникаторами; S = S??S??S1 . Множество отношений Att, определяющих структуру модели, это: Att={TT, TB, BT, TK?, TK?, TK?,K?T, K?T, K?T, T?S, T?S, T1S, ST}, TT?T?T – отношение, задающее структуру T через множество гиперссылок, связывающих его сайты: ; TB?T?B – отношение, задающее связи между T и B: ; и т.д. Множество атрибутов Char={Distr, Ind}. Показатель тематического распределения сайтов множества характеризует, какова доля элементов множества, тематически близких к тематике целевого множества; например, distr(B) – доля сайтов из B, близких к T. Множество показателей степени связности Ind характеризует множества отношений Att по степени связности самого целевого множества T всех остальных подмножеств; ind(TT)=?TT?/?T?, ind(BT)=?BT?/?B?.

Процедура построения KM : задание целевого множества T; формирование

сопутствующего множества U для заданного T; формирование множества ближайших окрестностей B; вычисление пороговых значений ? и ? и задание функции T_genre; формирование множества коммуникаторов K и множества-оболочки S; формирование множества отношений Att; определение множества значений атрибутов Ind и Distr.

U

K

T

S

B

distr(K)

distr(B)

ind(TK)

ind(KT)

ind(TB)

ind(BT)

distr(S)

ind(TS)

Диаграмма концептуальной модели академического фрагмента Веба

?=5, ?=10

top100.rambler.ru

www.harvard.edu

vak.ed.gov.ru

www.tvp.ru

www.rfbr.ru

www.ras.ru

www.mathnet.ru

www.forest.ru

www.expo.ras.ru

1,0

1,0

1,0

Веб-графом GFE(V,E), заданным на фрагменте Веба, называется

ориентированный граф без петель и кратных дуг, множество вершин которого является объединением целевого множества и множества веб-коммуникаторов V=T?K, а множество дуг E задается следующим образом: ?v1,v2?V: (v1,v2)?E ? ?<v1,v2>?TT?TK?KT?KK . Основные вопросы: находят ли иерархические отношения организаций-владельцев сайтов свое отражение в Вебе? насколько связны сайты T и как на их связность влияют сайты K? Предложен общий подход, апробированный на фрагментах академического и университетского Веба и фрагмента Веба органов госвласти Республики Карелия.

Исследования веб-графа, заданного на фрагменте Веба

Пример: административные дуги академического веб-графа

Значения функции связности на административном каркасе

Www.Ras.Ru (РАН)

Omn.Ras.Ru (ОМН)

Www.Febras.Ru (ДВО)

www.dncran.ru (ДагНЦ)

www.kscnet.ru (КамчНЦ)

Sc.Khv.Ru (ХНЦ)

Www.Ccas.Ru (ВЦ РАН)

Eimi.Imi.Ras.Ru (ПОМИ)

www.iyalidnc.ru (ИЯЛИ ДагНЦ)

Связность на административном подмножестве

Сайт

www.dncran.ru

www.krc.karelia.ru

www.kolasc.net.ru

www.chg.ru

www.psn.ru

www.ssc.smr.ru

www.spbrc.nw.ru

www.anrb.ru

www.ssc-ras.ru

Матрица смежности веб-графа региональных научных центров

№

15

18

19

20

21

22

23

26

27

15

18

19

20

21

1

1

22

23

26

1

1

27

Связность целевого множества

Университетский фрагмент Веба

Фрагмент Веба органов госвласти РК

Из 39 вершин: 24 содержатся в единственной КСС с диаметром 3; из остальных 15 13 - имеют только входящие дуги; 2 - имеют только исходящие дуги.

Из 56 вершин: 29 содержатся в единственной компоненте сильной связности (КСС) с диаметром 6; из остальных 27 21 - имеют только входящие дуги; 4 - изолированные, 2 - имеют исходящие и входящие дуги, но не входят в КСС.

Связность на целевом множестве и множестве веб-коммуникаторов

На множестве T

На множестве T?K

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

Пример: Фрагмент университетского Веба