__init__.py 44.2 KB
 Tiago Peixoto committed Oct 04, 2010 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014  or smaller than a given radius. See Also -------- triangulation: 2D or 3D triangulation random_graph: random graph generation lattice : N-dimensional square lattice Examples -------- >>> from numpy.random import seed, random >>> seed(42) >>> points = random((500, 2)) * 4 >>> g, pos = gt.geometric_graph(points, 0.3)  Tiago Peixoto committed Sep 02, 2011 1015  >>> gt.graph_draw(g, pos=pos, pin=True, size=(8,8), output="geometric.pdf")  Tiago Peixoto committed Oct 04, 2010 1016 1017  <...> >>> g, pos = gt.geometric_graph(points, 0.3, [(0,4), (0,4)])  Tiago Peixoto committed Sep 02, 2011 1018  >>> gt.graph_draw(g, size=(8,8), output="geometric_periodic.pdf")  Tiago Peixoto committed Oct 04, 2010 1019 1020  <...>  Tiago Peixoto committed Sep 02, 2011 1021 1022  .. image:: geometric.* .. image:: geometric_periodic.*  Tiago Peixoto committed Oct 04, 2010 1023 1024 1025 1026 1027 1028 1029  *Left:* Geometric network with random points. *Right:* Same network, but with periodic boundary conditions. References ---------- .. [geometric-graph] Jesper Dall and Michael Christensen, "Random geometric  Tiago Peixoto committed Dec 21, 2010 1030  graphs", Phys. Rev. E 66, 016121 (2002), :doi:10.1103/PhysRevE.66.016121  Tiago Peixoto committed Oct 04, 2010 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053  """ g = Graph(directed=False) pos = g.new_vertex_property("vector") if type(points) != numpy.ndarray: points = numpy.array(points) if len(points.shape) < 2: raise ValueError("points list must be a two-dimensional array!") if ranges is not None: periodic = True if type(ranges) != numpy.ndarray: ranges = numpy.array(ranges, dtype="float") else: ranges = array(ranges, dtype="float") else: periodic = False ranges = () libgraph_tool_generation.geometric(g._Graph__graph, points, float(radius), ranges, periodic, _prop("v", g, pos)) return g, pos  Tiago Peixoto committed Nov 13, 2010 1054 1055 1056 1057 1058 1059 1060 1061 1062  def price_network(N, m=1, c=None, gamma=1, directed=True, seed_graph=None): r"""A generalized version of Price's -- or Barabási-Albert if undirected -- preferential attachment network model. Parameters ---------- N : int Size of the network.  Tiago Peixoto committed Aug 27, 2011 1063  m : int (optional, default: 1)  Tiago Peixoto committed Nov 13, 2010 1064  Out-degree of newly added vertices.  Tiago Peixoto committed Aug 27, 2011 1065  c : float (optional, default: 1 if directed == True else 0)  Tiago Peixoto committed Nov 13, 2010 1066 1067  Constant factor added to the probability of a vertex receiving an edge (see notes below).  Tiago Peixoto committed Aug 27, 2011 1068  gamma : float (optional, default: 1)  Tiago Peixoto committed Nov 13, 2010 1069  Preferential attachment power (see notes below).  Tiago Peixoto committed Aug 27, 2011 1070  directed : bool (optional, default: True)  Tiago Peixoto committed Nov 13, 2010 1071 1072  If True, a Price network is generated. If False, a Barabási-Albert network is generated.  Tiago Peixoto committed Aug 27, 2011 1073  seed_graph : :class:~graph_tool.Graph (optional, default: None)  Tiago Peixoto committed Nov 13, 2010 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087  If provided, this graph will be used as the starting point of the algorithm. Returns ------- price_graph : :class:~graph_tool.Graph The generated graph. Notes ----- The (generalized) [price]_ network is either a directed or undirected graph (the latter is called a Barabási-Albert network), generated dynamically by at each step adding a new vertex, and connecting it to :math:m other  Tiago Peixoto committed May 06, 2011 1088  vertices, chosen with probability :math:\pi defined as:  Tiago Peixoto committed Nov 13, 2010 1089 1090 1091  .. math::  Tiago Peixoto committed May 06, 2011 1092  \pi \propto k^\gamma + c  Tiago Peixoto committed Nov 13, 2010 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110  where :math:k is the in-degree of the vertex (or simply the degree in the undirected case). If :math:\gamma=1, the tail of resulting in-degree distribution of the directed case is given by .. math:: P_{k_\text{in}} \sim k_\text{in}^{-(2 + c/m)}, or for the undirected case .. math:: P_{k} \sim k^{-(3 + c/m)}. However, if :math:\gamma \ne 1, the in-degree distribution is not scale-free (see [dorogovtsev-evolution]_ for details).  Tiago Peixoto committed May 06, 2011 1111 1112 1113 1114 1115 1116 1117  Note that if seed_graph is not given, the algorithm will *always* start with one node if :math:c > 0, or with two nodes with a link between them otherwise. If :math:m > 1, the degree of the newly added vertices will be vary dynamically as :math:m'(t) = \min(m, N(t)), where :math:N(t) is the number of vertices added so far. If this behaviour is undesired, a proper seed graph with :math:N \ge m vertices must be provided.  Tiago Peixoto committed Nov 13, 2010 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132  This algorithm runs in :math:O(N\log N) time. See Also -------- triangulation: 2D or 3D triangulation random_graph: random graph generation lattice : N-dimensional square lattice geometric_graph : N-dimensional geometric network Examples -------- >>> from numpy.random import seed, random >>> seed(42) >>> g = gt.price_network(100000) >>> gt.graph_draw(g, layout="sfdp", size=(12,12), vcolor=g.vertex_index,  Tiago Peixoto committed Sep 02, 2011 1133  ... output="price-network.pdf")  Tiago Peixoto committed Nov 13, 2010 1134 1135 1136  <...> >>> g = gt.price_network(100000, c=0.1) >>> gt.graph_draw(g, layout="sfdp", size=(12,12), vcolor=g.vertex_index,  Tiago Peixoto committed Sep 02, 2011 1137  ... output="price-network-broader.pdf")  Tiago Peixoto committed Nov 13, 2010 1138 1139  <...>  Tiago Peixoto committed Sep 02, 2011 1140 1141  .. image:: price-network.* .. image:: price-network-broader.*  Tiago Peixoto committed Nov 13, 2010 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152  Price networks with :math:N=10^5 nodes. **Left:** :math:c=1, **Right:** :math:c=0.1. The colors represent the order in which vertices were added. References ---------- .. [yule] Yule, G. U. "A Mathematical Theory of Evolution, based on the Conclusions of Dr. J. C. Willis, F.R.S.". Philosophical Transactions of the Royal Society of London, Ser. B 213: 21–87, 1925,  Tiago Peixoto committed Dec 21, 2010 1153  :doi:10.1098/rstb.1925.0002  Tiago Peixoto committed Nov 13, 2010 1154 1155 1156  .. [price] Derek De Solla Price, "A general theory of bibliometric and other cumulative advantage processes", Journal of the American Society for Information Science, Volume 27, Issue 5, pages 292–306, September 1976,  Tiago Peixoto committed Dec 21, 2010 1157  :doi:10.1002/asi.4630270505  Tiago Peixoto committed Nov 13, 2010 1158  .. [barabasi-albert] Barabási, A.-L., and Albert, R., "Emergence of  Tiago Peixoto committed Dec 21, 2010 1159 1160  scaling in random networks", Science, 286, 509, 1999, :doi:10.1126/science.286.5439.509  Tiago Peixoto committed Nov 13, 2010 1161 1162  .. [dorogovtsev-evolution] S. N. Dorogovtsev and J. F. F. Mendes, "Evolution of networks", Advances in Physics, 2002, Vol. 51, No. 4, 1079-1187,  Tiago Peixoto committed Dec 21, 2010 1163  :doi:10.1080/00018730110112519  Tiago Peixoto committed Nov 13, 2010 1164 1165 1166 1167 1168 1169  """ if c is None: c = 1 if directed else 0 if seed_graph is None:  Tiago Peixoto committed May 06, 2011 1170 1171 1172  g = Graph(directed=directed) if c > 0: g.add_vertex()  Tiago Peixoto committed Nov 13, 2010 1173  else:  Tiago Peixoto committed May 06, 2011 1174 1175  g.add_vertex(2) g.add_edge(g.vertex(1), g.vertex(0))  Tiago Peixoto committed Nov 13, 2010 1176 1177 1178 1179 1180 1181  N -= g.num_vertices() else: g = seed_graph seed = numpy.random.randint(0, sys.maxint) libgraph_tool_generation.price(g._Graph__graph, N, gamma, c, m, seed) return g