Как присвоить вес узлу в ориентированном сетевом графе и рассчитать эффективный вес узла

Моя проблема:

  1. У меня есть набор узлов, некоторые узлы соединены ребрами направления.
  2. Я хочу присвоить веса каждому узлу и каждому ребру.
  3. Наконец, я хотел бы рассчитать эффективные веса узлов на основе влияния связанных узлов.

Предыстория:

  1. В настоящее время я использую JUNG для решения своей проблемы.
  2. Я просмотрел пакет JUNG edu.uci.ics.jung.algorithms.scoring. Но не уверен, что они помогут мне достичь моих целей.

java graph algorithm graph-algorithm jung
person user1920253    schedule 20.12.2012    source источник
comment
Существует множество различных способов расчета [эффективных] весов узлов на основе влияния связанных узлов. JUNG действительно предоставляет несколько различных способов сделать это в указанном вами пакете. Уточните, пожалуйста, ваши требования: какими свойствами будут обладать веса узлов и веса ребер и как вы ожидаете, что они помогут определить «эффективные» веса узлов? Какой, по вашему мнению, должна быть семантика эффективных весов узлов? и Т. Д.   -  person Joshua O'Madadhain    schedule 22.12.2012
comment
Спасибо, Джошуа, что нашел время ответить.   -  person user1920253    schedule 26.12.2012
comment
(1) Допустим, у меня есть граф с множеством узлов с заданным риском для каждого узла. (2) Теперь некоторые из этих узлов соединены с другими ребрами направления. Эти края имеют переменную толщину. т. е. в зависимости от размера края результирующий риск будет варьироваться. (3) Теперь я хотел бы рассчитать эффективный риск этих узлов на основе связности. ‹br› Я видел оценочные пакеты JUNG. Я не уверен, какой алгоритм мне нужно использовать на основе моего требования. Не могли бы вы предложить, что было бы более подходящим, и есть ли образец реализации?   -  person user1920253    schedule 26.12.2012
comment
У вас все еще нет достаточно четкой спецификации для определения алгоритма. По сути, если вам нужен итеративный алгоритм в стиле PageRank, вам нужно определить, как риск для узла N в момент времени T определяется с точки зрения риска соседей N (предшественников? преемников?) в момент времени T-1. (Вы также должны быть в состоянии обосновать это определение на каком-то уровне.) Проще говоря, у вас нет четко определенных целей, поэтому невозможно посоветовать вам, как их достичь. Пока вы этого не сделаете, это, по сути, вопрос дизайна модели и не имеет ничего общего с каким-либо конкретным программным обеспечением.   -  person Joshua O'Madadhain    schedule 28.12.2012

Ответы (2)


arrow_upward
1
arrow_downward

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

person gerrytan    schedule 20.12.2012
comment
Истинный. JUNG уже предоставляет все эти базовые рамки для работы с графиком. Мой вопрос больше связан с алгоритмом Graph (например, PageRank или r EigenvectorCentrality) о том, как я могу назначить вес узла и использовать эти алгоритмы для определения влияния этих ребер. - person user1920253; 21.12.2012
comment
PageRank не использует веса узлов для определения оценок каждого узла. Если (например) вы считаете (начальные) веса узлов вероятностью старта в каждом узле, это распределение вероятностей на самом деле совершенно не имеет отношения к окончательному ответу, при условии, что граф сильно связан. (PageRankWithPriors — это другое дело.) - person Joshua O'Madadhain; 22.12.2012

arrow_upward
0
arrow_downward

На ум приходят два подхода:

  1. Добавьте поле weight в классы Node и Edge.

  2. Создайте два Maps. Один использует Nodes в качестве ключей, а другой использует Edges в качестве ключей. Затем сохраните weight в качестве значения.

person Code-Apprentice    schedule 21.12.2012
comment
Если мы говорим о JUNG PageRank и связанных с ним алгоритмах, в этом нет необходимости: веса узлов (как правило) назначаются алгоритмом, а веса ребер могут быть предоставлены в конструкторе, если это необходимо. - person Joshua O'Madadhain; 22.12.2012