Возможно, вы захотите ознакомиться с литературой по генерации графов и графообразования, в частности, работать в сетях без масштаба. быстрый интернет-поиск дал некоторые документы, которые могут иметь значение.
An overview реального мира динамических сетей WRT их свойства, подходящие модели и методы анализа.
The seminal paper по сетям без масштаба.
This survey article фокусируется на свойствах реалистичных графов, которые могут быть использованы в синтетическом генерации графов.
This paper Адресация уплотнения и сокращения диаметра, как утверждают авторы, часто встречаются на больших графиках реального мира. приводятся примеры тестов.
This paper сделок явно с генерированием синтетических графиков социальной сети.
рассматривают данные ссылки как несколько произвольные варианты. я бы ожидал огромного количества соответствующих ресурсов.
некоторые отрывочные мысли на высоком уровне: есть ли у вас какая-либо информация о (статистических) свойствах фактического графика, совокупных показателях весов или их статистического распределения? есть ли у вас какая-либо информация о свойствах вашей стратегии выборки (в частности, предвзятости)? ваши наблюдения отмечены по времени?
в случае, если у вас есть статистическая модель, посмотрите на оценку максимального правдоподобия. если у вас есть только наблюдаемые соединения, и если вы можете предположить, что они являются iid, вы можете применить метод бутстрапа к набору ваших наблюдений для оценки статистики свойств графа (например, среднее/дисперсия/и т. д. степени/связность/обхват/вес и т. д.). в зависимости от рассматриваемой меры этот трек может быть чрезмерным - предположим, что ваш набор наблюдений не является предвзятым и вместо этого вычисляет меру с данного графика.
передать эту информацию в генератор случайных графов, который позволяет инициализировать начальный график.
надеюсь, что этот контур помогает, как туманный, как он есть. с наилучшими пожеланиями.
Я думаю, что такой алгоритм должен быть очень дорогим. Я бы сказал, что нужно вычислить кратчайший путь между двумя узлами, и если он ниже, как заданная длина «treshold», скажем 2, существует высокая вероятность того, что эти узлы также могут соединиться ...но это сильно зависит от вашего контекста. В графике ссылок мое предположение может быть правильным, но для других сетей, вероятно, существует более высокая вероятность подключения более удаленных узлов и меньшая вероятность для близких узлов. Можете ли вы указать свой сценарий и почему для вас важно предсказать края? Это помогло бы для возможного построения алгоритма –
Предположим, что я хотел бы повторить рекомендации друзей Facebook, Google+ и LinkedIn. «Основываясь на ваших друзьях, вы можете знать следующих людей». Я хотел бы построить это для всей сети, вычисляя вероятность соединения для каждой пары. Я не думаю, что хочу пропустить пары, хотя мой окончательный вывод будет пропускать ссылки для сообщений ниже порогового значения для экономии дискового пространства. –
Я вижу. Хм ... Думаю, я сделаю 2-х ступенчатую BFS от человека. впоследствии можно рассчитать весь самый короткий путь (максимальная длина 2) между человеком любого слоя 2 человека. если длина пути 1 не существует, подсчитайте количество путей длины 2. «ребята» с наибольшим количеством путей длины 2 могут быть новыми краями ... мои мысли для этого. вы даже можете адаптировать его для более широких диапазонов и так далее. этот процесс должен быть дешевым, потому что это двухступенчатый BFS, и самый короткий путь с длиной max 2 также дешев. –