Нахального вымогательства пост.

Уважаемые участники! Я некоторым образом участвую в решении задачи о создании графов\сетей\таблиц взаимодействий похожих на заданные, но не являющихся их копиями ни в каком тривиальном смысле этого слова.

Например, заказчики хотят узнать, на что будет похож интернет, когда он станет в 4 раза больше (почему нельзя просто скопировать существующую картинку 4 раза, и как–нибудь склеить, можно рассказывать долго).

Мне для одной мысли нужен маленький пример сетки. А они, оказывается, в дефиците. Так вот, уважаемые исследователи (желательно из областей физики, химии, биологии — компьютерные сети нам нужны в последнюю очередь)!
Не могли бы вы мне показать какой–нибудь граф на 75–150 вершин, имеющий для вас прикладное значение?

Например, систему из цепочек питания. Или простенький метаболический цикл. Или оч. подробное взаимодействие продуктов распада урана. Рёбра графа могут иметь вес (даже лучше чтобы имели).

Заранее спасибо.

GD Star Rating
loading...
Tagged with →  

10 Responses to Нахального вымогательства пост.Уважаемые

  1. Peels:

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

    Ну а если тебя специфически волнуют химически–биологические формулы, посмотри на KEGG COMPOUND и смежные базы данных. У них есть такие штуки. Кнопочка «Mol file» внизу даст тебе описание молекулы, включая связи аля граф.

    Помимо этого при желании ты хоть утопись в данных, настолько их вокруг дофига.

  2. Ilmig:

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

    За идею спасибо. Молекула — это действительно сетка. Может быть, подойдёт.

  3. Peels:

    Ну хочешь — не хочешь, а от собственных принципов выборки ты никуда не спрячешься, даже если будешь изысканно выбирать эти свои собственные принципы выборки 🙂

  4. Ilmig:

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

  5. Yksiu:

    Схемы метрополитенов, железных дорог, всякого прочего транспорта уже пробовали?

  6. Peels:

    У графов не бывает «очевидных свойств». Любой паттерн, который ты найдешь в данной выборке графов будет изначально неочевидным, в том смысле что он скорее всего будет специфичен лишь для исследуемой популяции.

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

  7. Ilmig:

    У графов есть такие очевидные свойства как диаметр, распределение вершин по относительной плотности, итд.

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

    о. А это уже хорошая мысль, спасибо.

  8. Peels:

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

    Если тебе граф улиц нужен, тут недавно проходила ссылка на яндексовый конкурс этого года. Там как раз карта Москвы в виде графа задана, даже с весами. Хотя это тоже «большой» граф.

  9. Rekced:

    попробуй олиги например, АТТТАААГГГТЦГГЦЦ вот и готовый большой граф.

  10. Orenegue:

    генерируй случайную матрицу с неотрицательными компонентами. используй её как матрицу перехода. получишь граф с весами.

Добавить комментарий