Six Degrees of Captain America

Acting has Kevin Bacon, mathematics has Paul Erdos, but who is the most prolific Marvel character? Given a Marvel themed graph where each node is a superhero and each edge is a comic book, what is the best way to find the most connected character?

After dusting off my old Computer Science 101 textbook, I defined a character's connectedness as the average minimum distance (found via a breadth first search) to every node within the graph. With this definition in hand, Captain America won Marvel's most connected character award! In fact, even Chris Miller - the powerful and all knowing Sheriff of Anchorage, Alaska - has a close connection to Captain American!

Photo