• Введение
• Относительно предыдущих работ
  • Закон Зифа-Парето-Юла и степенной закон
  • Теоретико-графовые методы
  • Эксперименты
  • Результаты
• Описание паука
• Программа
  • create_all(dir)
  • add_to_merge()
  • add_to_graph()
  • add_to_fond()
  • is_distinkt()
  • location.wsc
• Заключение
• Некоторые определения теории графов

В 1991 г. сотрудники Европейского института физики частиц (CERN), занятые созданием системы передачи гипертекстовой информации через Интернет, выбрали язык SGML в качестве основы для нового языка разметки гипертекстовых документов. Этот язык - самое известное из приложений SGML - был назван HTML (HyperText Markup Language, "язык разметки гипертекста"). А первым (и долгое время единственным) графическим браузером в те далекие времена была программа Mosaic, разработанная в научном учреждении -- Национальном центре суперкомпьютерных приложений США (National Center for Supercomputer Applications -- NCSA). А между тем коммерческое освоение WWW не заставило себя долго ждать. В начале 1994 г. группа разработчиков браузера Mosaic под предводительством Джеймса Кларка, выпустила первую версию коммерческого браузера Netscape (начиная с версии 2.0 - Netscape Navigator). С этого момента начался экспоненциальный рост WWW, продолжающийся по сей день. С ростом количества Веб-страниц пришли такие "проблемы" как поиск, просмотр, хранение информации, ее упорядочивание и др. И начались исследования. Было установлено, что для решения подобных проблем эффективнее представлять Веб в виде ориентированного графа, узлами которого являются веб-страницы, а дугами - гиперссылки между ними. Можно указать еще несколько причин для построения и изучения этого графа:

• Разработка стратегий прохода по Вебу
• Анализ поведения веб-алгоритмов, которые используют информацию о ссылках. Например, что можно сказать о распределении и развитии значений рангов страниц (Page Rank) в подобных графах.
• Предсказание развития таких веб-структур как двудольные ядра, веб-кольца, и улучшенные алгоритмы для их описания и организации.
• Предсказание возникновения новых феноменов в этом графе

Моя работа основывается на исследовании 2000 года. Тогда был построен граф, состоящий более чем из 200 миллионов узлов и 1,5 биллионов дуг. Масштаб этого эксперимента превышает в 5 раз все предыдущие крупнейшие исследования, которые использовали данные 1997 года, состоящие из 40 миллионов узлов. Это исследование показало некоторые свойства этого графа, такие как диаметр, распределение степеней вершин, компоненты связности и макроскопическую структуру.

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

В девяностые годы прошлого века Веб начали рассматривать как граф. Проводилось много исследований, но я бы хотела рассказать о более глобальном, которое было проведено в 2000 году сотрудниками компаний AltaVista, IBN Almaden Research Center, Compaq Systems Research Center. Их работа называлась "Graph structure in the web" полный ее текст можно найти здесь (копия). Все предыдущие исследования можно разделить на две группы - (1) исследование Веба на предмет степенного распределения и (2) работы по применению теоретико-графовых алгоритмов к Веб-графу.

В ряде контекстов наблюдались распределения с обратным полиномиальным хвостом. Наиболее ранние наблюдения принадлежат Парето в контексте экономических моделей. Впоследствии подобное статистическое поведение наблюдалось в контекстах литературоведческого словаря, социологических моделей и проч. Исследования связаны со степенным законом, определяемым на положительных целых числах, причем вероятность значения i пропорциональна 1/ik, для некоторого положительного k. Не так давно распределения по степенному закону наблюдались в связи с различными аспектами Веба. Во-первых, степенные законы характеризуют поведение пользователей в Вебе в двух связанных между собой, но двойственных друг другу формах:

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

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

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

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

Подтвердилась точка зрения, что связанные и сильно связанные компоненты являются значимыми объектами. Теоретико-графовые методы используются для поиска [Kleinberg, Brin and Page], просмотра и хранения информации. Предполагается, что лучшая характеристика структуры Веба позволит больше сказать о каждой из этих областей.

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

Все эксперименты проводились с использованием программного обеспечения Conntctivity Scever 2, разработанном в Compaq Systems Research Center; обрабатывались данные, представленные Altavista. CS2 получает на входе данные от "паука" ("паук" собирает такую информацию о Вебе, как страницы и ссылки о них) и создает представление Веб-графом, порожденным страницами из данных в форме базы, состоящей из URLов, которые связаны друг с другом входящими и исходящими ссылками. Более того, граф дополняется теми URLами, которые были "достигнуты" по крайней мере 5 раз, т.е. если URL был "достигнут" пяти раз он становится недействительным.

CS2 - это улучшенный основной Connectivity Server (CS1), определенный для двух важных случаев. Во-первых, он значительно улучшил сжатие URLов и ссылок. Во-вторых, CS2 обеспечивает дополнительную функцию в виде host database. Например, в CS2 легко получить все входящие ссылки для данного узла, или все вхлодящие ссылки с удаленных host'ов.

В основном, данные Altavista собраны из большого количества источников, включая добровольные соглашения. "Паук" работает как ПВШ (поиск в ширину), но подчинен различным правилам, разработанным для избежания перегрузки веб-серверов, ловушек (искусственно недостижимых путей), избежания или обнаружения спама и т.д. Каждое построение индекса (готовой базы) Altavista основывается на собранных данных, которые были отфильтрованы - удалены дубликаты, спамовые страницы и прочее. Затем индекс развивается - удаляются недействительные ссылки, добавляются новые страницы, обновляются уже включенные страницы… CS2 может рассматриваться как множество всех страниц, хранящихся в индексе в данный момент времени. Заметим, что из-за многочисленности начальных точек, возможен граф с множеством компонент связности. CS2 использует три основных алгоритма:

• Поиск в ширину
• WCC - алгоритм, который находит слабо связанные компоненты. Алгоритм WCC просто находит все связанные компоненты в неориентированном Веб-графе.
• SCC - алгоритм, находящий сильно связанные компоненты

WCC и SCC являются модификациями ПВШ.

Степенные последовательности. Первый эксперимент был проведен для проверки того, что распределения степеней исхода и степеней захода соответствуют степенным законам. Эксперименты проводились на данных, собранных "пауком" в мае и октябре. Результаты показали заметное соответствие между ними и похожими экспериментами над данными двух годичной давности [Kumar, 99]. В самом деле, в случае со степенью захода, экспонента степенного закона примерно равна 2,1, как показали предыдущие исследования. Распределение степеней исхода также подчинено степенному закону, хотя экспонента примерно равна 2,72. Интересно отметить, что начальная часть сегмента распределения степеней исхода значительно отклоняется от степенного закона. Предполагается, что эти страницы с низкой степенью исхода следуют другому распределению, возможно Пуассона или комбинации Пуассона и степенного закона. Дальнейшие исследования должны уточнить эту комбинацию.

Неориентированные компоненты связности. В следующей серии экспериментов, Веб-граф трактуется как неориентированный граф (у дуг "отменяется" направление) и определяются размеры неориентированных компонент. С помощью алгоритма WCC была выделена гигантская компонента связности из 186 миллионов узлов, что составляет 91% всех узлов (из данных "паука"). Распределение размеров слабо связанных компонент также подчинено степенному закону с экспонентой примерно равной 2,5. Был выявлено следующее: если все ссылки на страницы со степенью захода, равной или больше пяти, удалить, граф будет содержать большую слабо связанную компоненту размером 59 миллионов узлов. Это показывает два интересных факта. Во-первых, связность в неориентированном Веб-графе очень гибка и не зависит от существования узлов с большой степенью захода. Во вторых, узлы, которые являются очень полезными и имеют тенденцию включать узлы с высоким PageRank, или узлы, которые считаются авторитетными и хорошими "центрами", внедрены в граф, который хорошо связан и без них. Последний факт может помочь в понимании того, почему алгоритмы типа HITS [Kleinberg] быстро сходятся.

Сильно связанные компоненты. В 1999 году [Albert, Jeond, Barabassi] заключили, что диаметр Веб-графа равен 19, и поэтому возможно добраться с одной страницы до другой за малое количество кликов. Чтобы проверить это надо выделить сильно связанные компоненты в ориентированном Веб-графе. Алгоритм SCC выделил несколько компонент связности, одна из которых размером в 56 миллионов узлов (это около 28% от всех страниц), остальные же меньше по размеру. Распределение размеров сильно связанных компонент также подчинено степенному закону.

ПВШ со случайным стартом. Алгоритм ПВШ запускался два раза на случайной выборке из 570 стартовых узлов (эти стартовые узлы лежат в сильно связанной компоненте), один раз в "прямом" направлении (как это сделал бы браузер) и один раз в "обратном", следуя по ссылкам в обратном направлении. Каждый из стартов показал острое бимодальное поведение: он либо "затухал", после достижения маленького множества узлов (в 90% случаев это множество имеет меньше 90 узлов, в крайних случаях в него входят несколько сотен тысяч узлов), или он "взрывался", покрывая около 100 миллионов узлов (но никогда полные 186 миллионов). Для части стартовых узлов, и прямые и обратные проходы ПВШ "взорвались", каждое покрытие приблизительно равно 100 миллионов узлов. Совокупные распределения узлов, собранных в этих проходах ПВШ, показывают, что истинная структура Веб-графа должна быть несколько более тонкой чем "маленькое мировое" явление, в котором браузер может пройти от любой веб-страницы до любого другой несколькими кликами. Более подробное обяъснение смотрите в разделе "Результаты".

Распределения Зифа против степенного распределения. Распределение Зифа - обратно полиномиальная функция рангов, а не величин. Например, если бы встречались степени захода только 1,4 и 5, то степенной закон был бы обратым полиномиалом этих величин, тогда как распределение Зифа было бы обратым полиномиалом рангов этих величин: т.е. обратым полиномиалом для 1,2 и 3. Распределение степеней захода больше похоже на распределение Зифа, чем на распределение по степенному закону.

Теперь соединим все результаты экспериментов. Учитывая, что множество сильно связанных компонент (SCC) содержит 56 млн узлов из 186 млн узлов гигантской слабосвязанной компоненты (WCC), используем алгоритм ПВШ, чтобы оценить позиции оставшихся узлов. Отправные точки, для которых прямой ПВШ "взрывается", находятся или в SCC, или во множестве IN, которое имеет следующее свойство: есть направленный путь от каждого узла IN ко всем узлам SCC. Симметрично, есть множество OUT, состоящее из всех отправных точек, для которых обратный ПВШ "взрывается"; есть направленный путь от любого узла в SCC к любому узлу OUT. Таким образом, прямой ПВШ от любого узла из SCC или IN "взорвется", также как обратный ПВШ со стартовыми узлами из SCC или OUT. Анализируя прямой и обратный ПВШ от 570 случайных отправных точек, мы можем вычислить число узлов, которые находятся в SCC, IN, OUT или ни одном из них.

Эти размеры этих компонентов такие:

Другие наблюдения. Рассмотрим вероятность того, что для вершин (u,v) существует путь от u до v. Для ориентированного Веб-графа эта величина равна 24%, для неориентированного - только 28%. Это приводит к интересному заключению: для случайно выбранных стартового узла и конечного узла, найти путь между ними мы можем лишь в четверти раз. Но если этот путь существет, его длина примерно 16. Однако, расстояние может быть значительно меньше - в среднем оно равно 7.

Диметр SCC примерно равен 28. Аналогично, максимальная длина кратчайшего пути равна 530, но, вероятно, существенно больше: если кратчайшая Tube подключает самую отдаленную страницу IN к самой отдаленной странице OUT, не проходя через SCC, максимальная длина кратчайшего пути, будет близка к 905.

В этом разделе я расскажу каким образом будет построен Уральский граф. Пауком назовем комплекс программ, который это выполнит. Рассмотрим граф, узлы которого соответствуют статическим веб-страничам, а дуги - гиперссылкам между ними. Этот граф назовем Веб-графом. Его можно представлять ориентированным и неориентированным (отмена ориентации ребер). Веб-страница называется Уральской, если она расположена на уральском сервере. Список ip-адресов уральских серверов можно получить разными путями, например найти в базах RIPN адреса, выделенные уральскому региону, но тогда "границы" окажутся несколько размытыми, ведь при распределении ip-адресов георафические границы почти не учитываются; или опросить всех достаточно крупных уральских провайдеров, а их МНОГО. Дальше возникает вопрос - с чего начать? Исследователи пользовались данными, собранными AltaVista, а у нас в регионе каталогов, которые бы полностью охватывали множество уральских страничек, очень мало. Можно привести в пример каталог UralWeb. Хочу уточнить, что учитывать мы будем только URL'ы протокола http. То есть у нас есть органичивающий признак - ip-адрес и точка старта - каталог UralWeb. Паук будет работать следующим образом:

1. Паук находит ссылки и складывает их в базу...
2. затем он их обрабатывает.
Эти этапы повторяются, пока все страницы не будут просмотрены. Этот цикл закончится так как у нас конечный граф. Хочу подчеркнуть, что url это "имя" веб-страницы (вершины), также url характеризует ссылку (ребро) - когда мы говорим о ссылке на страничку мы обычно не указываем источник этой ссылки, но с точки зрения теоретико-графовых терминов это неправильно - ребро это две вершины, поэтому здесь я буду указывать оба url'а. Программная структура Паука следующая:

Используемые таблицы:
Fond.dbf - это таблица, в которой содержатся еще не просмотренные страницы. Ее структура такая:

	url		C(100);	&& это поле хранит еще не просмотренный url (url=вершина Веб-графа)
	prev_url	C(100);	&& это поле хранит предыдущий url - из которого по гиперссылке мы достигли url
	ip		N(10);	&& ip-адрес страницы в десятичном виде.
	time_load	N(3);	&& время загрузки в секундах
	state		C(20);	&& состояние low available (try_count>0), available
	try_count	N(1);	&& количество попыток загрузки. Максимум = 5
	links		N(5);	&& количество ссылок
	date		T;	&& дата последней попытки загрузки
	

aaa.bbb.ccc.ddd = 256³*aaa+256²*bbb+256¹*ccc+ddd

Indistinct.dbf - таблица, содержащая "глухие" странички - которые не удалось загрузить. Структура таблицы такая же как в Fond.dbf.

Merge.dbf - таблица, содержащая неотфильтрованные странички. Ее структура такая:

	url		C(100);	&& это поле хранит еще не просмотренный url (url=вершина Веб-графа)
	prev_url	C(100);	&& это поле хранит предыдущий url - из которого по ссылке мы достигли url
	ip		N(10);	&& ip-адрес страницы в десятичном виде.

Graph.dbf - эта таблица содержит уральские странички, по которым будет проводится анализ Уральского Веба.

	url		C(100);	&& это поле хранит еще не просмотренный url (url=вершина Веб-графа)
	prev_url	C(100);	&& это поле хранит предыдущий url - из которого по ссылке мы достигли url
	ip		N(10);	&& ip-адрес страницы в десятичном виде.
	time_load	N(3);	&& время загрузки в секундах
	state	C(20);	&& состояние
	all_links		N(5);	&& количество ссылок
	date		T;	&& дата последней попытки загрузки
	in_deg		N(10);	&& для исследования
	out_deg		N(10);	&& для исследования
	

Ural2.dbf - таблица, содержащая ip-адреса уральского региона.

	n_ip	N(10);	&& номер сети
	ip_c	N(10);	&& количество адресов в сети
	comment	C(50);	&& коментарий
	

Используемые процедуры:

0. Create_all() - создает все таблицы, кроме Ural2.dbf, которая есть изначально. Устанавливает каталог, в который все будет сохранятся.
1. add_to_merge() - устанавливает связь с Интернетом, из таблицы Fond.dbf берет по очереди все страницы и все ссылки (которые, в свою очередь являются "именами" достижимых вершин) с каждой страницы складывает в таблицу Merge.dbf . try_count просмотренных страниц становится равным 0. Если страницу просмотреть не удалось, try_count увеличивается на 1.
2. add_to_graph() - все просмотренные страницы из Fond.dbf (try_count=0) добавляем в таблицу Graph.dbf, все "глухие" страницы (try_count=5) добавляем в Indistinct.dbf . Из таблицы Fond.dbf эти страницы удаляются.
3. add_to_fond() +convert()+search() - "пробегает" по Merge.dbf и уральские ссылки добавляет в Fond.dbf. Функция convert() преобразует ip-адрес из dotted decimal notation в десятичное число. Функция search() проверяет, входит ли данный ip-адрес в множество уральских адресов. Затем в Merge.dbf удаляет все строки.
4. is_distinkt()процедура проверки на дублирование страниц. После того, как из Merge.dbf добавили в Fond.dbf непросмотренные страницы, надо проверить, есть ли они в Graph.dbf. Если уже есть, то надо удалить их из Fond.dbf .

PROCEDURE create_all(dir)
SET DEFAULT TO (dir)

CREATE TABLE fond FREE ;
(url C(100),;
 prev_url C(100),;
 ip N(10),;
 time_load N(3),;
 state C(20),;
 try_count N(1),;
 links N(5),;
 date T)
 
SELECT fond
COPY STRUCTURE TO indistinct

INSERT INTO fond (url,prev_url,ip,time_load,size,state,date,try_count,links) ;
VALUES ("http://www.uralweb.ru/map/","http://www.uralweb.ru",3269628427,0,'0','unchecked',DATETIME(),0,0)
INDEX ON url TO f_url

CREATE TABLE graph FREE ;
(url C(100),;
 prev_url C(100),;
 ip N(10),;
 time_load N(3),;
 state C(20),;
 all_links N(5),;
 date T,;
 in_deg N(10),;
 out_deg N(10))
INDEX ON url TO g_url

CREATE TABLE merge FREE ;
(url C(100), prev_url C(100), ip N(10))

ENDPROC
	

m.oSh = CREATEOBJECT("WScript.Shell")
m.curImage = m.oSh.RegRead("HKCU\Software\Microsoft\Internet Explorer\Main\Display Inline Images")
m.curVideo = m.oSh.RegRead("HKCU\Software\Microsoft\Internet Explorer\Main\Display Inline Videos")
m.curAnima = m.oSh.RegRead("HKCU\Software\Microsoft\Internet Explorer\Main\Play_Animations")
m.curSound = m.oSh.RegRead("HKCU\Software\Microsoft\Internet Explorer\Main\Play_Background_Sounds")
m.oSh.RegWrite("HKCU\Software\Microsoft\Internet Explorer\Main\Display Inline Images","no")
m.oSh.RegWrite("HKCU\Software\Microsoft\Internet Explorer\Main\Display Inline Videos","no")
m.oSh.RegWrite("HKCU\Software\Microsoft\Internet Explorer\Main\Play_Animations","no")
m.oSh.RegWrite("HKCU\Software\Microsoft\Internet Explorer\Main\Play_Background_Sounds","no")

add_to_merge()

m.oSh.RegWrite("HKCU\Software\Microsoft\Internet Explorer\Main\Display Inline Images",m.curImage)
m.oSh.RegWrite("HKCU\Software\Microsoft\Internet Explorer\Main\Display Inline Videos",m.curVideo)
m.oSh.RegWrite("HKCU\Software\Microsoft\Internet Explorer\Main\Play_Animations",m.curAnima)
m.oSh.RegWrite("HKCU\Software\Microsoft\Internet Explorer\Main\Play_Background_Sounds",m.curSound)
*----------------------------------------------------------------

PROCEDURE add_to_merge()
CLOSE TABLES 
USE fond ALIAS fond IN 1

SELECT fond
m.oIE = CREATEOBJECT("InternetExplorer.Application")
m.oIE.Visible = .f.
SCAN 
	m.i = 0
	m.t = SECONDS()
	m.oIE.Navigate(fond.url)
	DO WHILE m.i < 30 AND m.oIE.ReadyState < 4
		m.i = m.i + 1
		WAIT TIMEOUT 1
 	ENDDO 
 	m.t = SECONDS() - m.t

 	IF 100 > LEN(m.oIE.LocationURL) 
 		sp = SPACE(100 - LEN(m.oIE.LocationURL))
 	ELSE 
 		sp = '' 
 	ENDIF 
 	s = m.oIE.LocationURL + sp 
	IF m.oIE.ReadyState < 4 OR s <> fond.url THEN 
  		REPLACE fond.state WITH 'not available'
 		REPLACE fond.try_count WITH try_count+1
 	ELSE 
 		IF try_count > 0 THEN 
	 		REPLACE fond.state WITH 'low available'
	 	ELSE 
		 	REPLACE fond.state WITH 'available'
	 	ENDIF 
	 	REPLACE fond.try_count WITH 0 
	 	REPLACE fond.time_load WITH m.t
		m.oL = m.oIE.Document.links
		REPLACE fond.links WITH m.oL.length
		FOR i=0 TO m.oL.length - 1
			INSERT INTO merge (url,prev_url) VALUES (m.oL.item(i).href,fond.url)
		ENDFOR			
 	ENDIF 
 	REPLACE fond.date WITH DATE()
ENDSCAN
m.oIE.Quit()
ENDPROC
	

PROCEDURE add_to_graph()
CLOSE TABLES
USE fond ALIAS fond IN 1
SELECT fond 
SCAN FOR try_count=0 OR try_count=5
IF fond.try_count=0 THEN 
	INSERT INTO graph (url,prev_url,ip,time_load,size,state,all_links,date) ;
	VALUES (fond.url,fond.prev_url,fond.ip,fond.time_load,fond.size,fond.state,fond.links,fond.date)
ELSE 
	INSERT INTO indistinct (url,prev_url,ip,time_load,size,state,all_links,date) ;
	VALUES (fond.url,fond.prev_url,fond.ip,fond.time_load,fond.size,fond.state,fond.links,fond.date)
ENDIF 
ENDSCAN 
DELETE FROM fond WHERE try_count=0 OR try_count=5
PACK IN fond
ENDPROC	
	

*-----------------------------------------------------------
&& переводит ip адрес (strip) в десятичное число
FUNCTION convert(strip) 
	m.n = 0
	m.tmp = 1
	m.j = 1
	DO WHILE AT('.',strip,m.j)>0   
	  m.i = AT('.',strip,m.j)
	  m.n = m.n*256 + VAL(SUBSTR(strip,m.tmp,m.i-m.tmp))
	  m.tmp = m.i+1
	  m.j = m.j + 1
	ENDDO 	
	  m.n = m.n * 256+ VAL(SUBSTR(strip,m.tmp))
RETURN m.n
ENDFUNC 
*-----------------------------------------------------------
&& ищет в таблице ural2 данный ip адрес
FUNCTION search(x)
	m.bool = .f.
	SET NEAR ON 
	SELECT ural2
	SEEK x IN ural2
	IF ural2.n_ip<=x AND x<=ural2.n_ip + ural2.ip_c THEN 
		m.bool = .t.
	ELSE 
		SKIP -1
		IF ural2.n_ip<=x AND x<=ural2.n_ip + ural2.ip_c THEN 
			m.bool = .t.
		ENDIF 
	ENDIF 
 	SELECT merge 
RETURN m.bool
ENDFUNC 
*-----------------------------------------------------------
PROCEDURE add_to_fond()
SET NEAR ON
SET DEFAULT TO c:\kurs
CLOSE TABLES 
USE merge ALIAS merge IN 1
USE ural2 ALIAS ural2 IN 2 INDEX n_ip

m.oWL = CREATEOBJECT("Web.Location")
m.oDNS = CREATEOBJECT("DNSControl.DNS")

SELECT merge
SCAN
m.oWL.URL = merge.url
	IF m.oWL.protocol = "http" THEN 
		m.ipv4 = oDNS.NameToAddress(m.oWL.server)
		m.ip = convert(m.ipv4)
		IF search(m.ip) THEN 
			INSERT INTO fond (url,prev_url,ip,time_load,size,state,try_count,links) ;
			VALUES (merge.url,merge.prev_url,m.ip,0,'0','unchecked',0,0)
		ENDIF 			
	ENDIF 
ENDSCAN 
DELETE ALL IN merge
PACK IN merge
ENDPROC 	
	

CLOSE TABLES
USE fond ALIAS fond IN 1 INDEX f_url
USE graph ALIAS graph IN 2 INDEX g_url

SELECT fond
COPY TO ARRAY arrFond FIELDS url
m.dim_arr = RECCOUNT("fond")
m.i = 0

SELECT graph
SET EXACT ON 
FOR m.i=1 TO m.dim_arr
	IF SEEK(arrFond(m.i),"graph")=.t.
		DELETE FROM fond.dbf WHERE url = arrFond(m.i)
	ENDIF 
ENDFOR 
CLOSE TABLES
PACK fond.dbf
	

<?xml version="1.0" encoding="windows-1251"?>
<component>
  <registration
    progid="Web.Location"
    description=""
    classid="{F07D7EAD-A989-4bef-844E-17125059C48A}"/>
  <public>
    <property name="URL" get="get_URL" put="put_URL"/>
    <property name="protocol"/>
    <property name="server"/>
    <property name="port"/>
    <property name="path"/>
  </public>
  <script language="JScript">
  <![CDATA[
  var URL,protocol,server,port,path;
  function get_URL(){
    return(URL);
  }
  function put_URL(s){
    URL=s
    s.search(/(\w+):\/\/([^/:]+)(:\d*)?([^# ]*)/g);
    protocol = RegExp.$1;
    server=RegExp.$2;
    port = RegExp.$3;
    path = RegExp.$4;
  }
  ]]></script>
</component>	
	

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

Список ip-адресов уральских серверов можно получить разными путями, например найти в базах RIPN (Russian Institute for Public Networks) адреса, выделенные уральскому региону, или опросить всех достаточно крупных уральских провайдеров. Самые большие трудности у меня возникли с поиском (созданием) такого списка. Во-первых, на сайте RINP (http://www.ripn.net/) такой информации не оказалось. На сайте RIPE NCC (Reseaux IP Europeens Network Coordination Centre) (http://www.ripe.net/ , ftp://ftp.ripe.net/) с горем пополам нашлись адреса по России. Поэтому я решила воспользоваться вторым вариантом - разослать письма провайдерам. Многие отвечали довольно бодро, а ответы некоторых меня ошеломили - они утверждали, что ip-адреса это конфиденциальная информация (видимо, они еще не знают что такое WhoIs). На сегодняшний день я собрала базу ip-адресов, но она еще очень далека от идеала, поэтому вопрос с базой ip-адресов остается открытым.

На FoxPro, с использованием технологии WSC (Windows Scripting Component), был написан набор программ, позволяющий построить за обозримое время Уральский Веб-граф. Целью моей следующей работы будет анализ структуры этого графа.

Графом G(V,E)

называется совокупность двух множеств - непустого множества вершин V и множества E неупорядоченных пар различных элементов множества V (E - множество ребер).

Ориентированным графом

называется граф G(V,E), если элементами множества E являются упорядоченные пары. В этом случае элементы множества V называются узлами, а элементы множества E - дугами.

Веб-графом

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

Степенью исхода узла u

называется количество дуг, исходящих из u (u,v₁),...,(u,v_k).

Степенью захода узла u

называется количество дуг, ведущих в u(v₁,u),...,(v_k,u).

Маршрутом в графе

называется чередующаяся последовательность вершин и ребер v₀,e₁,v₁,e₂,v₂,...,e_k,v_k. Если все ребра различны, маршрут называется цепью. Если все вершины различны, маршрут называется простой цепью. Длиной цепи называется количество ребер в ней. Для ориентированныых графов цепь называется путем.

Расстоянием между вершинами u и v

называется длина кратчайшей цепи.

Диаметром графа

называется максимальное из расстояний.

Две вершины в графе связаны

если существует соединяющая их (простая) цепь. Компонента связности это множество вершин такое, что две любые вершины являются связанными. Рассмотрим ориентиорванный граф G(V,E) с узлами u и v. Говорят, что два узла u и v сильно связаны, если существует путь из u в v и из v в u. Компонентой сильной связности называется множество узлов такое, что два любых узла являются сильно связанными.