Looking for books or resources on basic practical graph theory

January 26, 2006 12:59 PM

Graph theory seems hot right now. Don't know much about it, though. If one wanted to learn some of the most practical, useable, and interesting results from the field where would one turn? Bonus points for applicability in social sciences and/or web apps. And, tangentially, if one was potentially interested in focusing on graph theory and the social sciences, where would one look at grad school?

You can assume an engineering-student level of familiarity of mathematics on my part, and no strong fear of proofs, though I really don't like wading through page after page dense with nothing but odd symbols defined 5 chapters ago and phrases like "where A is a multiply dense compact monotonic pharyngeal set with elements from B distributed comopitomically throughout."

I don't mind *writing* such things, though. :) And I'd also be interested in any assesments about the actual hotness or coolness of graph theory as a field.

posted by namespan to science & nature (12 comments total)

The bible of Social Network Analysis (the primary application of graph theory in the social sciences) is Wasserman and Faust's book "Social Network Analysis". THe other book you should look at is Peter Carrington et. al.'s new book, which is a bunch of papers that update the methods described in Wasserman and Faust.

The organization most relevant to applications in social science is INSNA: The International Network of Social Network Analysts. Their conference is always awesome and will include both the hardcore math and substnative applications.

The INSNA web page includes a list of graduate programs. A lot of people in this area have undergrad or graduate backgrounds in math or physics though they currently work in the social sciences (mostly sociology), so there's plenty of precedent if you decided it was something you wanted to pursue.

For major journals, the big one is Social Networks. Also check out the Journal of Social Structure, which is peer reviewed but published completely online and freely accessible to all. Connections, contains short and more topical papers. Also peer reviewed and available freely online.

If you can give me more direction in what you're looknig for, I may know of more resources you'll find helpful.

Disclaimer: IAASNA
posted by duck at 1:21 PM on January 26, 2006

Oh, and as to assessments: I like it, but as I said, IAASNA.
posted by duck at 1:22 PM on January 26, 2006

For what it's worth, in high school about 6 years ago I had an interest in graph theory. I emailed professors working in that area at the state university and found them to be extremely courteous, intelligent, and helpful individuals. They had no problems scheduling time for me to visit with them and learn around the field, and even provided me with a couple of books on the subject. You might try this route as a good starting point to learning more.
posted by striker at 1:44 PM on January 26, 2006

Speculation as to why graph theory is hot:

Graph theory is interesting now because it is computationally tractable now.

In the 80's, cheap personal computers became good enough to do complex speadsheets. This made a lot of people's lives much easier, particularly people who already worked with small sets of tabular data - accountants, scientists, etc. Back then, a computer might have 128k or even 2 MB of RAM. a 5 to 20 MB hard drive was usually enough space in that decade.

In the '90s, CPUs got a lot faster, memory got bigger, disks got bigger, and high speed networking started to replace modems. By the end of the '90s, we had GHz class CPUs, Gigabyte class hard drives, and a few hundred MB of RAM. You could get more disk and memory, but that was expensive, so most people didn't. Video games, and GPUs were a major growth area for the '90s as well.

In the middle of the '00s, you can get a fast dual core CPU, 2 GB of RAM, and a significant fraction of a terabyte of disk space for under $2000 if you build it yourself, and under $3000 if you let dell build it for you. (Macs are also very capable here, the new dual core iMac should be outstanding)

More importantly, you can either put Linux and MySQL on your box, or you can spend lots of money on Windows Server 2k3 and SQL Server. Either way, you end up with an industrial grade database that allows you to process vastly larger quantities of data than a spreadsheet does. This enables a wide variety of new applications, from the desktop to the server space.

Graph theory is relevant today because SQL databases impose very little form upon the data. A spreadhseet like Excel forces you to format your data in a two dimensional matrix. This is fine way to balance your checkbook, but a terrible way to keep track of which of your friends like each other, and which ones can't stand the others' company. Graph theory provides a set of tools that are very useful when combined with a relational database.

In conclusion, graph theory has existed for hundreds of years. Right now it does not require much training or cash to work with computational machinery that can address interesting practical graph theory problems.
posted by b1tr0t at 1:45 PM on January 26, 2006

http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
posted by jon_kill at 2:12 PM on January 26, 2006

jon_kill - you just made my day! I have owned at least two copies of Diestel's book and have given both away to co-workers. I was about to buy a third, but now I've got the PDF.
posted by b1tr0t at 2:25 PM on January 26, 2006

but a terrible way to keep track of which of your friends like each other, and which ones can't stand the others' company.

Not at all...we use matrices for exactly that. And you can go back and forth between a matrix and a graph pretty easily.
posted by duck at 2:41 PM on January 26, 2006

The recent hotness follows two related ideas, small world graphs and scale-free graphs. The appeal of these to people not rigorously inclined is that it appears that many graphs in the "real world" seem to share these similar properties. Whether this is useful or a scientific fad, remains to be seen, but in the mean time it is generating many applied and theoretical papers.

As an engineer I would look at graph theory from the algorithmic side first. Take a look at what kinds of algorithms are efficient to compute and which are not, e.g. shortest path is O(n^3) while traveling salesman is NP complete.

Graph theory can be easily tied to other branches of combinatorial math. Thus results from different fields are connected. So a good introductory book to graduate combinatorics might be a good thing to look at too.
posted by blueyellow at 2:57 PM on January 26, 2006

Oh, one more field that is making graphs hot is data mining. A lot of data collected these days has an intrinsic graph structure and people are trying to figure out if there are ways to mine that for useful information.
posted by blueyellow at 2:59 PM on January 26, 2006

namespan & blueyellow: I was a data mining research assistant for two years, working on mining network information form Instant Messaging data. One of the things we were looking for (amoungst other things) was the scale-free ability of these networks. You can take a look at some of our publications. You'll probably be most interested in our second published paper: Extracting Social Networks from Instant Messaging Populations.

To go along with your research, you'll want to have some data sets to play with, which you can easily request to have sent to you (which includes some of our network/connectionist data). It'll be much easier then collecting your own.

Let me also prefix this by saying that it's really easy to do 'cool' things with social networks/graph theory. It's so much fun to jump pump out graph after graph to see how things look. If you want any more info, just drop me a line and I'll point you in the right direction.
posted by jeresig at 4:43 PM on January 26, 2006

Sorry to go a little crazy with best answers here. This is all great stuff -- Thank You!
posted by namespan at 6:33 PM on January 26, 2006

Graph theory = totally hot. Unmentioned so far are the possible applications of it to Homeland Security types of problems. For example, much research is being done right now on modeling the spread of disease-- ie, what would happen if one SARS or H5N1 carrier came back from abroad. How many people would he come into contact with in a given day? What would the profile of these interactions be?

Or, it may be that a heavily-watched organization in another country is communicating with encrypted messages. But, from intercepting the directionality of the messages, and analyzing the latency of propagation between the nodes, perhaps you could route out a chain of command, or identify cells of affiliated individuals.

Currently, funding for scientific research is increasing very slowly (or even decreasing, if you measure against the increases of previous years, or the costs of inflation for certain types of health research) but increasing amounts of money are being shifted into "transitional" defense-related research.
posted by Maxwell_Smart at 8:17 PM on January 26, 2006