Textrank: дополнение pagerank для извлечения предложения с использованием networkx - PullRequest
Новая
       30

Textrank: дополнение pagerank для извлечения предложения с использованием networkx

5 голосов
/ 12 февраля 2012

Я пытаюсь реализовать алгоритм textrank для извлечения предложения, как описано здесь . Для этого нужно дополнить алгоритм PageRank взвешенными ребрами и заставить его работать на неориентированных графах. Реализация алгоритма Networkx PageRank позволяет мне легко интегрировать взвешенные ребра и, как говорят, преобразовывать ориентированные графы в неориентированные: см. здесь . Однако, когда я тестировал, он все еще использует ориентированный граф. Что мне здесь не хватает? Помощь очень ценится.

Пример: 

import networkx as nx
D=nx.DiGraph()
D.add_weighted_edges_from([('A','B',0.5),('A','C',1)])
print nx.pagerank(D)

Outpunt: {'A': 0,25974025929223499, 'C': 0,40692640737443164, 'B': 0,33333333333333331}

Ответы [ 2 ]

9 голосов
/ 12 февраля 2012

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

Алгоритм PageRank был разработан для ориентированных графов, но это алгоритм не проверяет направленность входного графа и выполнить на неориентированных графах путем преобразования каждого ориентированного ребра в ориентированный граф к двум ребрам.

Это говорит о том, что алгоритм PageRank предназначен для ориентированных графов, но его можно использовать для неориентированных графов. Для этого он преобразует ненаправленную сеть в направленную сеть, заменяя каждое ребро двумя направленными ребрами (вход и выход).

Поэтому, если вы дадите ему ориентированную сеть, он будет рассчитывать PageRank в соответствии с направленной структурой. Так что либо начните с ненаправленной сети: 

import networkx as nx

# Undirected Network
D = nx.Graph()
D.add_weighted_edges_from([('A', 'B', 0.5),('A', 'C', 1)])

# Default max number of iterations failed to converge for me
print nx.pagerank(D, max_iter=200)

# Outputs:
{'A': 0.48648648872844047, 'C': 0.32567567418103965, 'B': 0.18783783709051982}

или, если у вас уже есть направленная сеть, преобразуйте ее в неориентированную: 

import networkx as nx

# Directed Network
D = nx.DiGraph()
D.add_weighted_edges_from([('A', 'B', 0.5), ('A', 'C', 1)])

# Convert to undirected
G = D.to_undirected()

# Default max number of iterations failed to converge for me
print nx.pagerank(G, max_iter=200)

# Outputs:
{'A': 0.48648648872844047, 'C': 0.32567567418103965, 'B': 0.18783783709051982}
0 голосов
/ 02 октября 2012

Хорошую реализацию алгоритма TextRank в python можно найти здесь . Если вы хотите использовать этот сценарий, вам нужно заранее запустить nltk.download (), чтобы установить необходимые файлы данных, как описано здесь .

...