Graph reduction

Let us consider graph1:
eblaC Graph reduction

g1 = {4612 <-> 4613, 4613 <-> 4614, 4642 <-> 4612, 4614 <-> 4522, 4798 <-> 4642, 4522 <-> 4376, 4536 <-> 4798, 4798 <-> 4996, 4376 <-> 4201, 4338 <-> 4536, 4813 <-> 4996, 4201 <-> 4043, 4074 <-> 4338, 4813 <-> 4735, 4043 <-> 3813, 3796 <-> 4074, 4646 <-> 4735, 3711 <-> 3813, 3665 <-> 3796, 4646 <-> 4585, 3711 <-> 3450, 3509 <-> 3665, 4584 <-> 4585, 3119 <-> 3450, 3177 <-> 3509, 4662 <-> 4584, 3119 <-> 2911, 2890 <-> 3177,4729 <-> 4662, 2911 <-> 2714, 2642 <-> 2890, 4729 <-> 4753, 2551 <-> 2714, 2641 <-> 2642, 4875 <-> 4753, 2518 <-> 2551, 4972 <-> 4875, 2481 <-> 2518, 5081 <-> 4972, 2365 <-> 2481, 4967 <-> 5081, 2320 <-> 2365, 4938 <-> 4967, 2310 <-> 2320, 4937 <-> 4938, 2215 <-> 2310, 2310 <-> 2317, 4942 <-> 4937, 2053 <-> 2215, 2315 <-> 2317, 4923 <-> 4942, 1943 <-> 2053, 2315 <-> 2316, 4922 <-> 4923, 1942 <-> 1943, 2329 <-> 2316, 4880 <-> 4922, 2329 <-> 2248, 4721 <-> 4880, 2248 <-> 2249, 4673 <-> 4721, 4683 <-> 4721, 2249 <-> 2246, 4672 <-> 4673, 4508 <-> 4683, 2246 <-> 2191, 4831 <-> 4672, 4507 <-> 4508, 2191 <-> 2093, 4779 <-> 4831, 2093 <-> 2052, 4551 <-> 4779, 4717 <-> 4779, 2052 <-> 2000, 4551 <-> 4409, 4489 <-> 4717, 2000 <-> 1961, 4274 <-> 4409, 4323 <-> 4489, 1961 <-> 1950, 4224 <-> 4274, 4084 <-> 4323, 1950 <-> 1951, 4223 <-> 4224, 3876 <-> 4084, 1951 <-> 1957, 4336 <-> 4223, 3769 <-> 3876, 1957 <-> 1948, 4336 <-> 4069, 4232 <-> 4336, 3704 <-> 3769, 1948 <-> 1949, 3767 <-> 4069, 4103 <-> 4232, 3545 <-> 3704, 2054 <-> 1949, 3561 <-> 3767, 4055 <-> 4103, 3409 <-> 3545, 2054 <-> 1996, 3415 <-> 3561, 3899 <-> 4055, 3408 <-> 3409, 1996 <-> 1997, 3415 <-> 3377, 3898 <-> 3899, 3425 <-> 3408, 2043 <-> 1997, 3345 <-> 3377, 3905 <-> 3898, 3461 <-> 3425, 2043 <-> 2128, 3277 <-> 3345, 3689 <-> 3905, 3410 <-> 3461, 2091 <-> 2128, 3277 <-> 3105, 3459 <-> 3689, 3360 <-> 3410, 2091 <-> 1946, 2923 <-> 3105, 3458 <-> 3459, 3254 <-> 3360, 1946 <-> 1838, 2822 <-> 2923, 2923 <-> 2894, 3458 <-> 3460, 3239 <-> 3254, 1725 <-> 1838, 2772 <-> 2822, 2894 <-> 2788, 3407 <-> 3460, 3238 <-> 3239, 1725 <-> 1531, 2771 <-> 2772, 2788 <-> 2598, 3406 <-> 3407, 1531 <-> 1342, 2480 <-> 2598, 3514 <-> 3406, 1342 <-> 1276, 2480 <-> 2402, 3321 <-> 3514, 3514 <-> 3504, 1219 <-> 1276, 2402 <-> 2400, 3153 <-> 3321, 3504 <-> 3272, 1219 <-> 1090, 2400 <-> 2401, 3042 <-> 3153,3023 <-> 3272, 1090 <-> 1035, 2793 <-> 3042, 3084 <-> 3042,2850 <-> 3023, 997 <-> 1035, 2424 <-> 2793, 3008 <-> 3084, 2739 <-> 2850, 997 <-> 960, 2134 <-> 2424, 3007 <-> 3008, 2578 <-> 2739, 2739 <-> 2645, 960 <-> 961, 1914 <-> 2134, 2488 <-> 2578, 2645 <-> 2356, 1656 <-> 1914, 2278 <-> 2488, 2195 <-> 2356, 1655 <-> 1656, 2277 <-> 2278, 2195 <->2023, 1896 <-> 2023, 1895 <-> 1896};

gx = Graph[g1];
we1 = Select[SortBy[{VertexList[g1], DegreeCentrality[g1]}[Transpose], Last], #[2] == 1 &][[All, 1]];

we11 = Table[we1[[i]] -> i, {i, 1, Length[we1]}];
we2 = Select[SortBy[{VertexList[g1], DegreeCentrality[g1]}[Transpose],Last],#[2] == 3 &][[All, 1]];
we22 = Table[we2[[i]] -> i + 11, {i, 1, Length[we2]}];
gx = Graph[g1(,GraphLayout[Rule]”SpringEmbedding”),VertexLabels -> Join[we11, we22]];
graph1 = HighlightGraph[gx, {Style[we2, Red], Style[we1, Yellow]}, VertexSize -> 2]

How to reduce the graph1 to graph2?. Graph2: x = {1 <-> 12, 12 <-> 4, 12 <-> 20, 20 <-> 7, 20 <-> 18, 18 <-> 11, 18 <-> 19, 19 <-> 10, 19 <-> 17, 17 <-> 14, 14 <-> 8, 14 <-> 6, 17 <-> 16, 16 <-> 13, 13 <-> 3, 13 <-> 5, 16 <-> 15, 15 <-> 2, 15 <-> 9};

graph2 = Graph[Reverse[x], GraphLayout -> “SpringEmbedding”,VertexLabels -> “Name”]

e0Ump Graph reduction

I have such an algorithm but it works relatively slowly (I need it to very large networks).
Designation of nodes are accidental and does not matter.

Let’s block ads! (Why?)

Recent Questions – Mathematica Stack Exchange