Python에서 가장 효율적인 그래프 데이터 구조는 무엇입니까?

Python에서 가장 효율적인 그래프 데이터 구조는 무엇입니까?

---

파이썬에서 큰 (10 ^ 7 노드) 그래프를 조작 할 수 있어야합니다. 각 노드 / 에지에 해당하는 데이터는 최소한의 문자열입니다. 메모리 및 속도 측면에서 가장 효율적인 방법은 무엇입니까?

dict의 dict는 더 유연하고 구현하기 간단하지만 직관적으로 목록 목록이 더 빠를 것으로 기대합니다. 목록 옵션은 또한 데이터를 구조와 별도로 유지해야하는 반면 dicts는 다음과 같은 종류의 것을 허용합니다.

graph[I][J]["Property"]="value"

무엇을 제안 하시겠습니까?

---

예, 제가 효율성이란 무엇을 의미하는지 좀 더 명확하게 말 했어야했습니다. 이 특별한 경우에는 랜덤 액세스 검색이라는 의미입니다.

데이터를 메모리에로드하는 것은 큰 문제가 아닙니다. 그것은 단번에 끝났습니다. 시간이 많이 걸리는 부분은 노드를 방문하여 정보를 추출하고 관심있는 메트릭을 측정 할 수 있습니다.

각 노드를 클래스로 만드는 것을 고려하지 않았지만 (속성은 모든 노드에 대해 동일 함) 오버 헤드의 추가 레이어를 추가 할 것 같습니까? 나는 누군가가 공유 할 수있는 유사한 사례에 대해 직접적인 경험이 있기를 바랐습니다. 결국 그래프는 CS에서 가장 일반적인 추상화 중 하나입니다.

---

나는 당신이 NetworkX 를 보는 것을 강력히 옹호합니다 . 전투 테스트를 거친 전쟁 말이며 대부분의 '연구'유형이 네트워크 기반 데이터 분석을 수행해야 할 때 도달하는 최초의 도구입니다. 노트북에서 문제없이 수십만 개의 모서리가있는 그래프를 조작했습니다. 그 기능이 풍부하고 사용하기 매우 쉽습니다. 기본 구현의 세부 사항보다는 당면한 문제에 더 집중할 수 있습니다.

예 에르 되시-RENYI 랜덤 그래프의 생성 및 분석

"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

시각화도 간단합니다.

더 많은 시각화 : http://jonschull.blogspot.com/2008/08/graph-visualization.html

---

Even though this question is now quite old, I think it is worthwhile to mention my own python module for graph manipulation called graph-tool. It is very efficient, since the data structures and algorithms are implemented in C++, with template metaprograming, using the Boost Graph Library. Therefore its performance (both in memory usage and runtime) is comparable to a pure C++ library, and can be orders of magnitude better than typical python code, without sacrificing ease of use. I use it myself constantly to work with very large graphs.

---

As already mentioned, NetworkX is very good, with another option being igraph. Both modules will have most (if not all) the analysis tools you're likely to need, and both libraries are routinely used with large networks.

---

A dictionary may also contain overhead, depending on the actual implementation. A hashtable usually contain some prime number of available nodes to begin with, even though you might only use a couple of the nodes.

Judging by your example, "Property", would you be better of with a class approach for the final level and real properties? Or is the names of the properties changing a lot from node to node?

I'd say that what "efficient" means depends on a lot of things, like:

• speed of updates (insert, update, delete)
• speed of random access retrieval
• speed of sequential retrieval
• memory used

I think that you'll find that a data structure that is speedy will generally consume more memory than one that is slow. This isn't always the case, but most data structures seems to follow this.

A dictionary might be easy to use, and give you relatively uniformly fast access, it will most likely use more memory than, as you suggest, lists. Lists, however, generally tend to contain more overhead when you insert data into it, unless they preallocate X nodes, in which they will again use more memory.

My suggestion, in general, would be to just use the method that seems the most natural to you, and then do a "stress test" of the system, adding a substantial amount of data to it and see if it becomes a problem.

You might also consider adding a layer of abstraction to your system, so that you don't have to change the programming interface if you later on need to change the internal data structure.

---

As I understand it, random access is in constant time for both Python's dicts and lists, the difference is that you can only do random access of integer indexes with lists. I'm assuming that you need to lookup a node by its label, so you want a dict of dicts.

However, on the performance front, loading it into memory may not be a problem, but if you use too much you'll end up swapping to disk, which will kill the performance of even Python's highly efficient dicts. Try to keep memory usage down as much as possible. Also, RAM is amazingly cheap right now; if you do this kind of thing a lot, there's no reason not to have at least 4GB.

If you'd like advice on keeping memory usage down, give some more information about the kind of information you're tracking for each node.

---

Making a class-based structure would probably have more overhead than the dict-based structure, since in python classes actually use dicts when they are implemented.

---

No doubt NetworkX is the best data structure till now for graph. It comes with utilities like Helper Functions, Data Structures and Algorithms, Random Sequence Generators, Decorators, Cuthill-Mckee Ordering, Context Managers

NetworkX is great because it wowrs for graphs, digraphs, and multigraphs. It can write graph with multiple ways: Adjacency List, Multiline Adjacency List, Edge List, GEXF, GML. It works with Pickle, GraphML, JSON, SparseGraph6 etc.

근사, 이분, 경계, 중심성, 클리크, 클러스터링, 채색, 구성 요소, 연결성,주기, 방향성 비순환 그래프, 거리 측정, 지배 집합, Eulerian, 동형, 링크 분석, 링크 예측, 매칭을 포함한 다양한 방사 알고리즘을 구현합니다. , 최소 스패닝 트리, 리치 클럽, 최단 경로, 순회, 트리.

참고 URL : https://stackoverflow.com/questions/1171/what-is-the-most-efficient-graph-data-structure-in-python