This workflow will create mid points of edges between polygons and delete outer ones called "LINKS":

arcpy.FeatureToLine_management(in_features="PGONS", out_feature_class="C:/SCRATCH/OUTLINES.shp", cluster_tolerance="", attributes="NO_ATTRIBUTES")
arcpy.Dissolve_management(in_features="OUTLINES", out_feature_class="C:/SCRATCH/edges.shp", dissolve_field="", statistics_fields="", multi_part="SINGLE_PART", unsplit_lines="DISSOLVE_LINES")
arcpy.FeatureVerticesToPoints_management(in_features="edges", out_feature_class="C:/SCRATCH/midpoints.shp", point_location="MID")
arcpy.SpatialJoin_analysis(target_features="midpoints", join_features="PGONS", out_feature_class="C:/SCRATCH/SJ.shp", join_operation="JOIN_ONE_TO_MANY")
arcpy.Dissolve_management(in_features="SJ", out_feature_class="C:/SCRATCH/links.shp", dissolve_field="TARGET_FID", statistics_fields="JOIN_FID FIRST;JOIN_FID LAST", multi_part="SINGLE_PART", unsplit_lines="DISSOLVE_LINES")
arcpy.SelectLayerByAttribute_management(in_layer_or_view="links", selection_type="NEW_SELECTION", where_clause='"FIRST_JOIN" = "LAST_JOIN_"')
arcpy.DeleteFeatures_management(in_features="links")

import arcpy,os
import networkx as nx
nodes="PGONS"
edges="LINKS"
G=nx.Graph()
with arcpy.da.SearchCursor(edges,("Shape@","FIRST_JOIN","LAST_JOIN_")) as cursor:
    for pG,f,t in cursor:
        G.add_edge(f,t)
        G[f][t]["Shape"]=pG
g=arcpy.Geometry()
geometryList=[pgon.boundary() for pgon in arcpy.CopyFeatures_management(nodes,g)]
curT = arcpy.da.InsertCursor("out_points",("F","T","SHAPE@"))
for f in G.nodes():
    outline=geometryList[f]
    aList=[]
    for t in nx.neighbors(G,f):
        p=G[f][t]["Shape"].firstPoint
        chainage = outline.measureOnLine(p)
        aList.append((chainage,f,t,p))
    aList.sort()
    for chainage,f,t,p in aList:
        curT.insertRow((f,t,p))
del curT

This workflow will create mid points of edges between polygons and delete outer ones called "LINKS":

arcpy.FeatureToLine_management(in_features="PGONS", out_feature_class="C:/SCRATCH/OUTLINES.shp", cluster_tolerance="", attributes="NO_ATTRIBUTES")
arcpy.Dissolve_management(in_features="OUTLINES", out_feature_class="C:/SCRATCH/edges.shp", dissolve_field="", statistics_fields="", multi_part="SINGLE_PART", unsplit_lines="DISSOLVE_LINES")
arcpy.FeatureVerticesToPoints_management(in_features="edges", out_feature_class="C:/SCRATCH/midpoints.shp", point_location="MID")
arcpy.SpatialJoin_analysis(target_features="midpoints", join_features="PGONS", out_feature_class="C:/SCRATCH/SJ.shp", join_operation="JOIN_ONE_TO_MANY")
arcpy.Dissolve_management(in_features="SJ", out_feature_class="C:/SCRATCH/links.shp", dissolve_field="TARGET_FID", statistics_fields="JOIN_FID FIRST;JOIN_FID LAST", multi_part="SINGLE_PART", unsplit_lines="DISSOLVE_LINES")
arcpy.SelectLayerByAttribute_management(in_layer_or_view="links", selection_type="NEW_SELECTION", where_clause='"FIRST_JOIN" = "LAST_JOIN_"')
arcpy.DeleteFeatures_management(in_features="links")

import arcpy, os
import networkx as nx

nodes="PGONS"
edges="LINKS"
G=nx.Graph()

with arcpy.da.SearchCursor(edges, ("Shape@","FIRST_JOIN","LAST_JOIN_")) as cursor:
    for pG,f,t in cursor:
        G.add_edge(f,t)
        G[f][t]["Shape"] = pG
g = arcpy.Geometry()
geometryList = [pgon.boundary() for pgon in arcpy.CopyFeatures_management(nodes,g)]
curT = arcpy.da.InsertCursor("out_points",("F","T","SHAPE@"))
for f in G.nodes():
    outline = geometryList[f]
    aList = []
    for t in nx.neighbors(G,f):
        p = G[f][t]["Shape"].firstPoint
        chainage = outline.measureOnLine(p)
        aList.append((chainage,f,t,p))
    aList.sort()
    for chainage,f,t,p in aList:
        curT.insertRow((f,t,p))
del curT