1
$\begingroup$

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

  • 4
    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.2011-08-30
  • 0
    Not every question about graphs is graph theory, and not every question about sets is set theory. In this case, this question is neither.2011-08-30
  • 4
    Hmm... from the title, I kind of expected the question to be about deep foundational issues and to involve things like [Aczel's axiom](http://en.wikipedia.org/wiki/Aczel%27s_anti-foundation_axiom). I guess I was wrong.2011-08-30
  • 0
    @Niel: I'm sorry to ask, but my English skills are failing on me: What is (tool-usage) and for what kinds of questions is this tag intended?2011-08-30
  • 0
    @Theo Buehler: I was looking at Asaf's comment above and wondered what tag would be appropriate. Nicola's question is really about what mathematical 'tool' is best to use for a certain job. I thought that this could be summed up in the phrase 'tool-usage'. On second thought it is perhaps a bit ambiguous (many would probably think of it referring to a piece of software, for instance); if you can think of a better phrase, I'm receptive.2011-08-30
  • 0
    @Niel: Thanks for the explanation. No, I don't know a better solution. On the other hand, I'm not sure I completely agree with Asaf's comment. Anyway, I'll let others discuss and deal with this matter.2011-08-30
  • 4
    The more I think about it, the more I'm starting to doubt that the question is mathematical in its nature.2011-08-30
  • 1
    @Niel: If this were on SO, I'd be inclined to tag it as [data-structures](http://stackoverflow.com/questions/tagged/data-structures) (and probably also [social-networking](http://stackoverflow.com/questions/tagged/social-networking)). Perhaps we could use such a tag here, or perhaps the problem is that the question really belongs elsewhere.2011-08-30
  • 0
    @Ilmari: indeed, I was struggling for a term that wasn't something like "foundations", which to me is consonant with data structures (but which is obviously not the right term for this question)! I would hesitate to apply the word "data structures" to this because it would not do to suggest that actual programming questions belong here; but can you think of a similar term that would fit? How does "Mathematical structures" sound (maybe a bit vague)?2011-08-30
  • 0
    @Asaf: discrete applied mathematics, perhaps, albeit of an elementary nature. We accept questions on mathematical physics and economics, so the fact that it's "for something else" isn't a problem. I think that so long as there is a reasonable way to answer such a question, at least pedagogically, then it can be construed as a question about mathematics.2011-08-30
  • 0
    @Niel: Physics is mathematical by nature, finance has a strong mathematical side as well. Representation as social structure? I'm not really sure.2011-08-30
  • 0
    That depends on what you call "math". Are graphs "math" only inasmuch as they involve "numbers" somehow, or is any abstract nd in-principle-formalisable investigation of structure "math"? I say the latter.2011-08-30
  • 0
    Combining the comments of Niel and Ilmari, I think it is safe to tag this as (mathematical-modeling). Added also (soft-question) because "Which is better" does not necessarily admit one true answer.2011-09-01

1 Answers 1

6

"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".