Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

for social network representation, what is better, sets or graphs ? What kind of feature the first gives that the second doesn't and viceversa?

share|cite|improve this question
A graph is a set that has additional structure -- specifically, it has structure representing the connections between its elements (and possible other information, such as the strength of the connection if it's a weighted graph). If you need to represent connections between elements you should use a graph representation of the problem. If you're doing computations, the fact of how to implement your graph on the computer is another question - there are at least three possible representations which offer different benefits and drawbacks. – Chris Taylor Aug 30 '11 at 9:25
Not every question about graphs is graph theory, and not every question about sets is set theory. In this case, this question is neither. – Asaf Karagila Aug 30 '11 at 9:32
Hmm... from the title, I kind of expected the question to be about deep foundational issues and to involve things like Aczel's axiom. I guess I was wrong. – Ilmari Karonen Aug 30 '11 at 10:48
The more I think about it, the more I'm starting to doubt that the question is mathematical in its nature. – Asaf Karagila Aug 30 '11 at 11:10
@Niel: If this were on SO, I'd be inclined to tag it as data-structures (and probably also social-networking‌​). Perhaps we could use such a tag here, or perhaps the problem is that the question really belongs elsewhere. – Ilmari Karonen Aug 30 '11 at 11:10
up vote 6 down vote accepted

"Which is better, graphs or sets" depends crucially on what limitations you're imposing on how you use these.

For instance, as a potential foundation for mathematics, sets can be used to do essentially anything if you put your mind to it. For instance, sets can be used to represent a graph. You can represent a graph as a set of labelled nodes, and the edges $u\text{-}v$ are represented by unordered pairs $\{u,v\}$ (which will be singleton sets in the case of self-loops). Or you can represent a graph as a set of labelled edges, where the nodes are given as collections of edges $\{e_1, e_2, \ldots, e_k\}$ which meet one another (and where each edge can belong to at most two such sets).

More powerful than graphs are hypergraphs, which generalize graphs in that each 'edge' can link multiple nodes. If you picture social circles of friends as overlapping sets of people, what you're envisioning is a hypergraph; but conversely, a hypergraph is little more than a collection of overlapping sets.

You could represent the circles on Google+ as a sort of directed hypergraph, where each edge consists of a mapping from a single individual to the people that follow them, or from a single individual to all of the members of one of their circles. And of course, these functions (which are set-valued functions) can also be represented with sets if you're so inclined.

So it will depend on how creative you want to be with the particular tool you have at hand. Certainly, a graph on a set of people is more useful and informative (but requires more work to describe) than just having a set of people; but this is not the limitation of what you can "do with sets".

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.