New Eden Topology - 2021 Update

For general discussion about EVE Online.
Forum rules
Discussions about EVE University should go in the E-Uni General Discussion subforum. If you have questions about joining EVE University, please contact our Personnel Department.
Post Reply
User avatar
Akira Zendragon
Member
Member
Posts: 242
Joined: 2006.06.30 17:47
Location: Portugal

New Eden Topology - 2021 Update

Post by Akira Zendragon »

A couple of days ago Conci Furiram asked in #incursions-officers discord if someone had updated this little gem http://schildwall.phbv3.de/topology.html from 2010.

With the formation of the Pochven region, 27 systems were moved from their original regions into Pochven, and this has resulted in some changes to the topology of New Eden. Most notably, the invasion of Niarja changed the Jita-Amarr route from 9 jumps to 46 jumps, and greatly increased the length of highsec routes connecting most parts of Amarr space to the rest of highsec. :ccp:

I have no idea if there have been other changes to the gate network since 2010, but the numbers suggest that the only change was the creation of Pochven.

I'm not going to be re-doing the whole thing, but I'm revisiting the first part, and then will be looking specifically to answer the question that triggered this, which is to determine optimal locations to stage/store incursion ships. That will be a follow-up post in the Incursions forum.

Part I - New Eden's network

New Eden's connected gate network (k-space minus Jove regions and Pochven) has:
  • 5174 systems
  • 6832 gate pairs
By modeling it as an undirected graph, and applying an "all-pairs shortest paths" algorithm, we can determine some properties of the gate graph, or parts of it, e.g. a specific region.

A lot of these properties derive from looking at "shortest paths", and the nomenclature can get confusing so let's simplify things a tiny bit and say that a route is the shortest path between system A and system B.

The length of the longest route is called the diameter of the graph, and is 99 jumps. There are 3 routes of length 99:
The 3 routes are all between Stain and Tenal and go around the "west" side of the map and never leave nullsec.

A more interesting property is radius. A graph's radius isn't necessarily half of the diameter, but is never less than half of the diameter. We can calculate it by taking the longest route possible from each system, and then taking the shortest of these routes.

The graph's radius is 56, same as it was before Pochven was created, but at that time, there was only one "shortest longest route" of length 56, and it started at Lansez (Khanid) , making it the "radial center" of the gate network.

Today we have 5 "radial centers", which is to say that from any of these 5 systems you can reach any other system in 56 jumps or less.
The other way to determine a center of the gate network is by looking at the lowest average length of the routes from that system. Following the original article's convention, lets call that the mean center.

Before the creation of Pochven it was Kaaputenen (The Citadel) with average of 26.3 jumps, today the mean center of the gate network is Amamake (Heimatar) with 25.4 average jumps.

Part II - The High-sec network

In the original post, the author also calculated the same metrics for a subset of the gate network, specifically contiguous High-sec space, meaning all HS space except for the HS islands, and considering only HS routes

Diameter: 74 (Up from 51)
Diameter Routes: Radius: 37
Radial centers: Before Pochven, radius was 27, and radial center was Algogille

Mean centers (19.9 average jump distance) These are closely followed by several neighbouring systems.
Rens (20.03 jumps) and Hek (20.12 jumps) are the most central trade hubs followed by Dodixie (22.68), Amarr (24.98) and Jita comes up last with 29.21 average jumps

Before Pochven, the mean center of HS was Kaaputenen, with an average 12.5 jumps, now its average distance is 27.08 jumps

Part III - Regional data

In the original 2010 article, the author provided us with a spreadsheet of regional data: https://spreadsheets.google.com/ccc?key ... 5Y2c&hl=en

(Edit: Seems like some of you have had issues accessing that, here's a copy of the original shee - https://docs.google.com/spreadsheets/d/ ... 8UeCo/edit)

In similar fashion I made a spreadsheet with updated numbers: https://docs.google.com/spreadsheets/d/ ... UH5GbYFbk/

As in the original, shortest routes may cross into other regions. For instance, the shortest route between Villore and Renyn (Essence) goes two jumps into Sinq-Laison.

- "All Regions" is the updated version of the original 2010 sheet.
- "HS - Regions (Excluding islands)" is the same calculations, but limited to HS systems and HS routes
- "HS - Grouped regions (Excluding islands)" has a smaller set of metrics for groups of HS space, eg: all Caldari HS
- "HS - Incursions (Excluding islands)" is similar to the previous one, but includes only routes that have incursion systems as destinations, based on the list of HS incursion spawns in our wiki https://wiki.eveuniversity.org/Constell ... rity_space

The last two sheets are mostly meant to address the original question of where to stage incursion ships, which will be the topic of an upcoming post in the Incursions forum
Last edited by Akira Zendragon on 2021.03.06 09:07, edited 1 time in total.
Incursions Officer
ImageImageImageImage
ImageImageImageImage
User avatar
Arin Mara
Member
Member
Posts: 224
Joined: 2020.07.10 13:53

Re: New Eden Topology - 2021 Update

Post by Arin Mara »

I had to close the Forum Post thrice to prevent myself from feinting... the amount of data is overwhelming! :D

What did you use to compute the distances? Can you show to raw data? What algorithm did you use to compute the distances? How long did it take to compute all the distances?

Napkin math tells me that if there are 5174 Systems and you want to compute all possible paths... that's super exponential! :D

I'm also denied access to the Original Google Docs, so I can't see the results.
User avatar
Akira Zendragon
Member
Member
Posts: 242
Joined: 2006.06.30 17:47
Location: Portugal

Re: New Eden Topology - 2021 Update

Post by Akira Zendragon »

Here's a copy of the original sheet: https://docs.google.com/spreadsheets/d/ ... sp=sharing

The raw data comes from the SDE (https://wiki.eveuniversity.org/Static_Data_Export). Specifically, I got Fuzzwork’s Postgres version of it and loaded up the DB to poke about a bit and figure out the data structure.

Relevant tables:
  • mapSolarSystems has solar system data
  • mapRegion has the region data
  • mapSolarSystemJumps has all the jumps between adjacent solar systems
  • chrFactions has the faction data, used for the last two sheets
  • mapConstellations has the constellation data -> Used to filter out the incursion constellations for the last sheet
I exported CSVs of mapSolarSystems and mapSolarSystemJumps, with only the relevant attributes, eg: solar system ID, name, regionID and region name from mapSolarSystems, and just origin and destination solarSystemIDs for mapSolarSystemJumps.

This second file, with solar system ID pairs is effectively an adjacency list that describes the graph of new eden gates. The first file was used to filter out things for individual regions and to convert the IDs to solar system names in the output.

Python is probably the go-to choice for this, but I'm a Ruby developer, so I used https://www.rubydoc.info/github/monora/rgl for the graph analysis.

Load up the CSV files, create the graph from the list of jumps and then comes the slow part, which is to do what's called the "All-pairs shortest-paths". In this case, for each of the 5174 system, run Dijktra's shortest paths algorithm to get all the shortest paths from that system. Takes a while, it's about 26.7 Million routes. I just left it running as I was working so I can't tell you if it took half an hour or 2 hours.

Then I transformed that into a list of (origin, destination, distance) triplets that I exported as a CSV. Loading that is much faster than recomputing the whole thing.

The analysis can be done in SQL if you load this CSV into the same database as the SDE, so you can filter out by region or whatever you want, but I did a lot of it in Ruby since I was exploring things in the process, and some of this wasn't that easy to do in SQL anyway.

The HS data is obtained by filtering the graph to exclude all non-HS systems to get the HS graph. Initially you get a graph that includes the islands, but you can filter out those by identifiyng each connected component of the graph (The graph library has a method for that). There is a big one, then several small ones, these are the islands. Remove all those from the graph and you get the contiguous HS graph.
On this graph, repeat the "All-pairs shortest-paths" run to get the HS routes. This one doesn't take so long, we have about 1.1M routes. Exported this to another CSV for the HS analysis.

From this point on, you don't need the graph anymore, you're just looking at the calculated routes.

For the incursions sheet, I got a list of HS constellations from the wiki, used the SDE data to get a list of systems, and filtered the HS routes to include only routes that have these incursion systems as destination.
Incursions Officer
ImageImageImageImage
ImageImageImageImage
User avatar
Vandron Fuji
Member
Member
Posts: 20
Joined: 2020.09.01 11:53

Re: New Eden Topology - 2021 Update

Post by Vandron Fuji »

I started reading it then my head hurt
Post Reply