Advertisements



The Hunt for the Wumpus Goes On in My Apartment

Most of my writing is either done at a branch of the Richmond Public Library or in my office in my apartment. The apartment is fairly large as these things go: two bedrooms, a full living room and dining room, and a tiny room that’s pretty much useless for anything other than a study. It has a tiny balcony running along the front (not big enough for a chair, alas) and steps leading down to the ground floor. The picture below is a diagram of the apartment; I’ve simplified things, leaving out closets, not bothering to make the proportions exact, and so forth.

Different routes between rooms in an apartment based more or less on mine.

Note in the figure that I put a dot in each room (as well as the hallway, the balcony, and the stairs, which are proxy for the front door), along with red lines connecting pairs of dots. These lines are “direct” connections in a sense: to get from my office to the bedroom, you must pass through the landing area and the hall (and possibly also the bathroom). Alternately, you could go onto the balcony, go to the living room, dining room…but you still have to go into the hall, just at a different starting point. If we think of each room not as a room but a node in a network, we have the beginnings of another way to represent my apartment. If we don’t worry about the size and shape of each room, only about the basic path a person must take to travel around the place, we can replace the floor plan above with a graph, as shown below.

A graph of my apartment: somewhat more abstract than the picture above. The spatial relationships between the different rooms (nodes) are close to how they are on the floor plan, but the routes are drawn to connect them more directly, since the walls are gone.

The graph is useless for arranging furniture, but it’s a bit simpler than the floor plan: the arrangement of walls and doorways are gone, replaced simply with nodes. Possibly other houses and apartments might have the same graph, even if the floor plan is very different! If you think I’m heading toward topology, you’re right: as with the stretchy shapes and lack of concern about distances, our graph is unworried about how many steps between bed and toilet (as important as that may be at 2 AM).

In fact, depending on what our goals are in the exercise, we can simplify things even further. The second bedroom (a “spare oom”, without a passage to Narnia) is a dead end: unlike any of the other rooms, you can’t go from it into any other spot except the hallway. Its location relative to other rooms is unimportant: as far as the graph is concerned, it can be located between kitchen and entryway (as shown above), or we can move it to a different spot, which the figure at the right shows. After breaking away from physical locations, the graph is simplified: the hallway is a hub with seven spokes, and the position of each node is picked only for convenience. We could just as easily arrange things differently, as long as each node is connected to other nodes properly. I haven’t allowed the links to overlap each other, though there’s no reason why not as long as we know they aren’t actually connecting.

The living room has two doors out onto the balcony, which is very pleasant in nice weather. I could possibly collapse the path from living room to balcony into one, since the starting and ending points are the same, but let’s think topologically. Like the center of a donut, the two ways out onto the balcony represent a topological “hole”: the two paths cannot be deformed into each other without hitting the wall, so this region of the apartment is not simply connected.

The cave system in "Hunt the Wumpus". Gregory Yob, the programmer of the original version, described the labyrinth as a "squashed dodecahedron". Each node is a room in the cavern, and is connected to exactly three other nodes.

My cats love the complicated network of paths they can follow through the apartment, hunting each other (and me) through the rooms. A classic computer game (which I learned to program in BASIC when in 5th grade) is called “Hunt the Wumpus”; in that game, the player is a hunter looking for a fierce monster in a cavern consisting of rooms laid out in the network shown. There are no graphics in the game, and the character you play is blinded by darkness: you can hear the Wumpus roaring if he’s in an adjacent chamber, but you can’t see where he is. As with my apartment graph, the distance between rooms and the size of each chamber is irrelevant: what’s important is the path you take, attempting to kill the Wumpus with arrows before the Wumpus finds and eats you.

Both the apartment and the Wumpus examples are kind of frivolous, but they illustrate some of the basic principles of graph theory: how different nodes (rooms) connect to each other. As with my research paper I wrote about Tuesday, the nodes could be switches or oscillators or brain cells, and the connecting lines could be chemical pathways, electrical wires, or whatever. The “shape” of the network is how many nodes are connected to each other (how clustered things are) and how large the network is as a whole, which is a measure of how many links a message must travel along from one side to the other (e.g., how many rooms to pass through to go from office to bedroom).

All-to-all coupling in a network with 5 nodes. The overlap in the links isn't another connection, since there isn't a blue dot (node) there.

My research paper with my friend Elana is based on the simplest kind of network: every node is connected with every other node. We picked this network for an obvious reason: it’s mathematically straightforward. We don’t have to worry about which node connects with which and why, and the behavior of the system as a whole should reflect a more realistic scenario. Many other models have been built on similar assumptions, so while it’s not the best choice possible, it works well to show the kinds of interesting phenomena our model is capable of describing.

My friend went to elementary school with Kevin Bacon, so I have two degrees of Kevin Bacon. Note that I am connected to my friend through several links (mutual friends), but we each have friends not shared by the other.

Another type of system, studied in detail by Steve Strogatz (whose work has largely concerned spontaneous synchronization) and his colleagues, is the small world network. You might be familiar with the “six degrees of separation” meme: that you are connected through no more than six links with any given other person in the world. That idea is a little too simplistic, but it contains some grains of truth, as Strogatz describes in his book Sync—you are connected to a number of friends, family, and acquaintances (which may be a large number in the Internet era), and all those people are connected to others, and so forth. The twist on that meme involves movie actors: how many degrees of separation are there between any movie actor and Kevin Bacon. I happen to have a friend who went to elementary school with Bacon, so I have two degrees of Kevin Bacon myself.

Similarly, my brother (a French horn player) was mentored by Michael Thompson, who has performed with Paul McCartney. So I have three degrees of separation with The Cute Beatle, and four with the rest of the Beatles (and practically every other major figure in pop music in the last 60 years). It’s not a close connection, of course, but it shows how one link (my brother’s mentor) opens up a whole network that has nothing to do with my daily life. My own field of theoretical physics is much closer to me: I have two degrees of separation with Einstein through several links, even though he died many years before I was born. (I calculated my Erdős number to be three several years ago, but I can’t remember now what path of authorship I followed to get there.)

Neurons in a mouse brain. Note how each cell acts as a node in a network, and may be connected in various ways with other cells.

Strogatz and colleagues found that small world networks may enable crickets and fireflies to coordinate: they each may only be receiving signals from a small handful of neighboring insects, but that’s enough. One outside link opens up a wider network, passing the message along to the next small group and so forth, until hundreds or thousands may be flashing and chirping simultaneously. Similarly, each brain cell isn’t connected to every other cell, yet they are able to carry the electrochemical messages that enable thought and other operations, coordinating across the entire cortex. As you can probably guess, Elana and I plan to extend our model into small world networks and possibly other network topologies. In other words, you haven’t heard the last of this from me yet. The hunt for the Wumpus goes on.

Advertisements

1 Response to “The Hunt for the Wumpus Goes On in My Apartment”


  1. 1 Kaleberg January 16, 2012 at 21:44

    It sometimes works in reverse. Architects and space planners often start by drawing connectivity graphs to ensure that the final room layout meets important functional requirements and avoids serious problems before starting to do a physical layout.


Comments are currently closed.



Advertisements

Please Donate

DrMRFrancis on Twitter


%d bloggers like this: