Re: Questions I would like the OkCupid data-mongers to answer

1

Neb, this is simply wonderful.


Posted by: heebie-geebie | Link to this comment | 02- 2-10 11:00 AM
horizontal rule
2

I think there would almost certainly be one enormous class, and a handful of two-person "new member contacts new member" classes.


Posted by: Eggplant | Link to this comment | 02- 2-10 11:04 AM
horizontal rule
3

So you may continue living your life now. You're welcome.


Posted by: Eggplant | Link to this comment | 02- 2-10 11:06 AM
horizontal rule
4

I offer this as a stop-gap; it's re-drawn from the data in here, but only looking at the largest connected component.


Posted by: Cosma Shalizi | Link to this comment | 02- 2-10 11:08 AM
horizontal rule
5

Oh, and a larger number of singleton classes.


Posted by: Eggplant | Link to this comment | 02- 2-10 11:09 AM
horizontal rule
6

4: Those are actual mutual relationships. The graph of prospects and hopefuls will be much different.


Posted by: Eggplant | Link to this comment | 02- 2-10 11:12 AM
horizontal rule
7

And now I'm done.


Posted by: Eggplant | Link to this comment | 02- 2-10 11:13 AM
horizontal rule
8

I like it that the entire front page is in italics now, but I think the comments should be too. Possibly bold italics.


Posted by: PGD | Link to this comment | 02- 2-10 11:16 AM
horizontal rule
9

Will this explain why so many polyamorous people on OkCupid are apparently interested in me?


Posted by: Criminally Bulgur | Link to this comment | 02- 2-10 11:18 AM
horizontal rule
10

9: Maybe you just clique with people?


Posted by: Eggplant | Link to this comment | 02- 2-10 11:26 AM
horizontal rule
11

Is there at least a good approximate solution to the longest-cycle problem? Otherwise we'll have to wait a bit while the OkCupid folks and their descendants try to satisfy your curiosity.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 11:27 AM
horizontal rule
12

I think there would almost certainly be one enormous class, and a handful of two-person "new member contacts new member" classes.

What about the class with enormous members?


Posted by: heebie-geebie | Link to this comment | 02- 2-10 11:31 AM
horizontal rule
13

I don't have a clue what Ben is asking in the second paragraph of the original post.


Posted by: Cyrus | Link to this comment | 02- 2-10 11:33 AM
horizontal rule
14

I don't have a clue what Ben is asking in the second paragraph of the original post.


Posted by: Cyrus | Link to this comment | 02- 2-10 11:33 AM
horizontal rule
15

To answer my own question: Yes.

Best known approximation for … digraphs: O(n / log n) [Alon, Yuster & Zwick 1995]


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 11:36 AM
horizontal rule
16

I'm not sure whether it reflects worse on heebie or on unfogged that, even upon receiving the metaphorical engraved invitation to make a math joke, the math professor went for the cock joke. You're fully asimilated now, heebs.


Posted by: KR | Link to this comment | 02- 2-10 11:37 AM
horizontal rule
17

12: I would suggest a depth-first search.


Posted by: Eggplant | Link to this comment | 02- 2-10 11:37 AM
horizontal rule
18

Breadth-first, actually.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 11:39 AM
horizontal rule
19

9: That happened to me too. First like five or six messages I got from people were from dudes with wives who are totally cool with them expressing their boundless love with others. Usually, this was phrased in the terms, "You can do whatever you want to me." Uh, thanks? For the permission?

I just kept responding that I'm just really trying to make an effort to date single people for a while.


Posted by: A White Bear | Link to this comment | 02- 2-10 11:40 AM
horizontal rule
20

Just just.


Posted by: A White Bear | Link to this comment | 02- 2-10 11:40 AM
horizontal rule
21

Usually, this was phrased in the terms, "You can do whatever you want to me."

That may be short-sighted. "Whatever you want" is a set that includes shaving-off one of his eyebrows, emptying his wallet, taking any nice kitchen appliances, and leaving.


Posted by: Moby Hick | Link to this comment | 02- 2-10 11:44 AM
horizontal rule
22

14: How big are the groups of people who are all connected by chains of contacts? (The jargon phrase is "connected component", which is actually fairly transparent for once.)


Posted by: Cosma Shalizi | Link to this comment | 02- 2-10 11:49 AM
horizontal rule
23

The paper cited in 18 advertises an "unofficial impact factor" of 1.47, which makes me wonder what the typical impact factor is among studies of penis size.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 11:49 AM
horizontal rule
24

19: I'm just curious as to what relative weight to give the following factors in explaining the phenomenon: (1) there being more polyamorous people in the real world than I think; (2) there being more polyamorous people on OkCupid than in the real world; (3) there being a hidden clue in my professed vegetarianism and love of the movie Sherman's March that I'm more likely to be down with swinging than others.


Posted by: Criminally Bulgur | Link to this comment | 02- 2-10 11:55 AM
horizontal rule
25

24: Or 2a -- polyamorous people on OkCupid contact more people than the regular amorous people.


Posted by: Moby Hick | Link to this comment | 02- 2-10 11:58 AM
horizontal rule
26

24: I think they look for profiles that don't say "I'm looking for a steady partner." Weirdly, I got just as many flat-out sexual solicitations (mostly from married men, some polyamorous and some with clueless/indifferent partners, though I'm not sure 100% of the former aren't really the latter) with my completely asexual ad this time around as I used to get as a 23-year-old advertising interest in sex w/no chaser. I think it's the absence of the words "looking for a partner/spouse/future co-parent" that turns them on.


Posted by: A White Bear | Link to this comment | 02- 2-10 12:01 PM
horizontal rule
27

From link in 18: Thus, a man with a short but wide penis would probably think of himself as having a small penis, and would be so thought of by others, too.

Any guesses as to the author's penis size/shape.


Posted by: JP Stormcrow | Link to this comment | 02- 2-10 12:01 PM
horizontal rule
28

25 too, yes. Married/partnered people seem (ime) to be a lot less afraid of rejection that single people. They have someone to go home to, and they can always blame rejection on their status rather than their attractiveness/whateverness.


Posted by: A White Bear | Link to this comment | 02- 2-10 12:03 PM
horizontal rule
29

than single people. Jesus, I need a nap.


Posted by: A White Bear | Link to this comment | 02- 2-10 12:03 PM
horizontal rule
30

28: I have no specific insights on OkCupid or polyamorous people. I just like categorizations that are exhaustive.


Posted by: Moby Hick | Link to this comment | 02- 2-10 12:04 PM
horizontal rule
31

Oh! Also, on OKC they have those statistics things. So I can have a totally asexual ad that's as off-putting as I can make it, but OKC will advertise my ad as horny! kinky! untraditional!


Posted by: A White Bear | Link to this comment | 02- 2-10 12:05 PM
horizontal rule
32

On the first question:

The length of the longest cycle is likely to be more or less accidental. It's the short cycles that are interesting. How many four-cycles are there: Alan has messaged Barbara has messaged Clive has messaged Donna has messaged Alan is interesting because it's likely that Barbara and Donna know each other.


Posted by: jim | Link to this comment | 02- 2-10 12:06 PM
horizontal rule
33

Good choice by BioMedCentral for the very first article in the first issue of their new "Women's Health" journal.


Posted by: Cryptic ned | Link to this comment | 02- 2-10 12:08 PM
horizontal rule
34

Yes, but Donna isn't speaking to Barbara because of what happened at the Olive Garden last July.


Posted by: Moby Hick | Link to this comment | 02- 2-10 12:09 PM
horizontal rule
35

24: You left out another possibility: (4) people looking to cheat who claim to be polyamorous.


Posted by: Cyrus | Link to this comment | 02- 2-10 12:09 PM
horizontal rule
36

Other thoughts from the author of the link in 18:

Years ago, a tennis partner of mine, about 60 years old or so, told me " I am attracted to young girls. I mean, really young girls. I could get in trouble from this attraction." He seemed perplexed by his attraction to young females. So was I. Through all these years I could never figure out why this would be true for him, and for other men I have discussed this with. Now, evolutionary psychology has come along and provided a theoretical structure of male and female desires, which explains why aging men would desire young, female partners.

Posted by: JP Stormcrow | Link to this comment | 02- 2-10 12:10 PM
horizontal rule
37

35: I don't see how that would apply to reasons for contacting CB. Also, AWB mentioned that in 26.


Posted by: Moby Hick | Link to this comment | 02- 2-10 12:12 PM
horizontal rule
38

Most of these people have links to their respective polyamours' own OkCupid profiles, so they're either legit or impressively conspiratorial.


Posted by: Criminally Bulgur | Link to this comment | 02- 2-10 12:16 PM
horizontal rule
39

Is it possible to imagine life without knowing the number and other characteristics of the classes so distinguished?

I bet the number of people in the kth largest connected component goes as a power law in k.

(OK, I admit it, I'm just hoping to provoke more commenting from Cosma.)


Posted by: essear | Link to this comment | 02- 2-10 12:18 PM
horizontal rule
40

Maybe the polyamorous people are just friendly people who think you are nice too, but then they find out they were wrong and they become saddened.


Posted by: Natilo Paennim | Link to this comment | 02- 2-10 12:22 PM
horizontal rule
41

Sorry I rejected you, Natilo, but I had to do it. I'm a jerk.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 12:24 PM
horizontal rule
42

40: I have no idea if it correlates or not, but certainly polyamory would be easier the less picky you are. That's why I was thinking they might contact more people than the rest of OkCupid.


Posted by: Moby Hick | Link to this comment | 02- 2-10 12:26 PM
horizontal rule
43

42: Not that I meant to suggest CB was especially attractive to the less-picky.


Posted by: Moby Hick | Link to this comment | 02- 2-10 12:27 PM
horizontal rule
44

43: Good save.


Posted by: Natilo Paennim | Link to this comment | 02- 2-10 12:28 PM
horizontal rule
45

44: Yes, I'm going back to the other thread. 42 came out poorly.


Posted by: Moby Hick | Link to this comment | 02- 2-10 12:29 PM
horizontal rule
46

It's OK. By "less picky" I just assumed he meant "less likely to be intimidated by the overwhelmingly awesome."


Posted by: Criminally Bulgur | Link to this comment | 02- 2-10 12:36 PM
horizontal rule
47

(OK, I admit it, I'm just hoping to provoke more commenting from Cosma.)

I wish this ever worked.


Posted by: Sifu Tweety | Link to this comment | 02- 2-10 12:39 PM
horizontal rule
48

All these years, and it's still fucking hilarious that the famous sex researchers are Masters and Johnson. Shame that Dr. Bristols was unavailable.


Posted by: JRoth | Link to this comment | 02- 2-10 12:44 PM
horizontal rule
49

Would you be amused to learn that the modern procedure for the vasectomy was invented by Dr. Blanc?


Posted by: Moby Hick | Link to this comment | 02- 2-10 12:58 PM
horizontal rule
50

(The jargon phrase is "connected component", which is actually fairly transparent for once.)

I had remembered the phrase "connected component", but wasn't sure it meant what I wanted to say, and I figured talking about it in terms of equivalence classes would be fairly clear. In re Eggplant's guess that there would only be one (excluding new user–to–new user contacts), that itself would be interesting, but I would expect that if you control for geography (someone contacts someone in sf, then moves to nyc and contacts someone there) you could get regional groups—and again, it would be interesting still if only geography accounted for them.

Is there at least a good approximate solution to the longest-cycle problem?

This is something else I wasn't sure of—whether there's an efficient algorithm for detecting this. I take it the answer is "no". However! I was able to divert myself by attempting to think up algorithms.


Posted by: nosflow | Link to this comment | 02- 2-10 1:33 PM
horizontal rule
51

What you really want, nosflow, is not the connected components; it is more like the output of the Shi-Malik algorithm, where normalized cuts allow you to segment the graph into richly interconnected subgraphs.


Posted by: Eggplant | Link to this comment | 02- 2-10 1:51 PM
horizontal rule
52

the output of the Shi-Malik algorithm

The stuff that Google turns up for this looks pretty interesting.


Posted by: essear | Link to this comment | 02- 2-10 1:55 PM
horizontal rule
53

normalized cuts allow you to segment the graph into richly interconnected subgraphs

This sounds thrillingly sensual.


Posted by: nosflow | Link to this comment | 02- 2-10 2:25 PM
horizontal rule
54

Just skimmed it -- that's a great paper. One of those ideas that seems obvious in hindsight but in fact first required hundreds of person-years to have been spent in sporadically fruitful, graph-theoretic headbanging.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 2:36 PM
horizontal rule
55

There's more: Random walks! Piecewise constant eigenfunctions! Okay, these aren't as sensual.


Posted by: Eggplant | Link to this comment | 02- 2-10 2:36 PM
horizontal rule
56

All the world's a graph, and we are merely richly interconnected subgraphs.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 2:37 PM
horizontal rule
57

54: Yeah, like pagerank, it has a bit of that forehead slapping effect.


Posted by: Eggplant | Link to this comment | 02- 2-10 2:38 PM
horizontal rule
58

Likes: random walks on the beach, piecewise constant eignenunctions at sunset.


Posted by: Bave Dee | Link to this comment | 02- 2-10 2:41 PM
horizontal rule
59

Is this an axis I see before me?


Posted by: fake accent | Link to this comment | 02- 2-10 2:41 PM
horizontal rule
60

eignenunctions

Mathematicians get these just before they die.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 2:42 PM
horizontal rule
61

Extreme eigenunctions.


Posted by: Bave Dee | Link to this comment | 02- 2-10 2:43 PM
horizontal rule
62

dammit standpipe


Posted by: Bave Dee | Link to this comment | 02- 2-10 2:43 PM
horizontal rule
63

62: If you wouldn't have said anything, I would have assumed you were amending 60, not being pwned.


Posted by: Moby Hick | Link to this comment | 02- 2-10 2:45 PM
horizontal rule
64

That would have been unctuous.


Posted by: Bave Dee | Link to this comment | 02- 2-10 2:47 PM
horizontal rule
65

But not extremely so.


Posted by: Moby Hick | Link to this comment | 02- 2-10 2:47 PM
horizontal rule
66

This sounds thrillingly sensual.

I know, right? We should totes revive the Unfogged journal club. Where by "revive" I mean "invent, along the lines of that one late-night discussion of Indians and boatbuilding and Pacific Islanders and whatnot".


Posted by: essear | Link to this comment | 02- 2-10 2:49 PM
horizontal rule
67

If you wouldn't have said anything

You just gave me an aneurysm.


Posted by: nosflow | Link to this comment | 02- 2-10 2:51 PM
horizontal rule
68

along the lines of that one late-night discussion of Indians and boatbuilding and Pacific Islanders and whatnot

By which I mean this.


Posted by: essear | Link to this comment | 02- 2-10 2:56 PM
horizontal rule
69

Was the reason because of the grammaticalness?


Posted by: Not Prince Hamlet | Link to this comment | 02- 2-10 2:57 PM
horizontal rule
70

69 to 67.


Posted by: Not Prince Hamlet | Link to this comment | 02- 2-10 2:57 PM
horizontal rule
71

67: Is "If you would have said nothing" that much better?


Posted by: Moby Hick | Link to this comment | 02- 2-10 2:57 PM
horizontal rule
72

For you homework tonight, Bave, compute the eigenunctions of the co-redemptrix.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 2:59 PM
horizontal rule
73

Someone explain to me why you can't detect longest cycles using a depth-first search that keeps track of the distance of the current from the starting vertex.1 Or is it just that that's horribly inefficient?

1. This is where I was going to explain what I was thinking of at greater length before I decided not to.


Posted by: nosflow | Link to this comment | 02- 2-10 3:06 PM
horizontal rule
74

So are we closer now than ever before to answering the angels and pin question?


Posted by: fake accent | Link to this comment | 02- 2-10 3:08 PM
horizontal rule
75

Someone explain to me why you can't detect longest cycles using a depth-first search that keeps track of the distance of the current from the starting vertex.

Are you assuming the starting vertex is on the largest cycle?


Posted by: essear | Link to this comment | 02- 2-10 3:53 PM
horizontal rule
76

If not, perhaps you might wish to consider explaining what you were thinking of at greater length.


Posted by: essear | Link to this comment | 02- 2-10 3:53 PM
horizontal rule
77

No, I wasn't, though I am assuming that the largest cycle is reachable from the starting vertex.

I am considering your explaining at greater length, but I think I'm on the verge of doing some reading and I don't want to mess with that too much.


Posted by: nosflow | Link to this comment | 02- 2-10 3:55 PM
horizontal rule
78

Oh! Also, on OKC they have those statistics things. So I can have a totally asexual ad that's as off-putting as I can make it, but OKC will advertise my ad as horny! kinky! untraditional!

You mean the stuff that shows up in the "Personality" tab? That's not based on your profile, it's based on all the match questions you've answered. AFAIK the only way to change that is to either answer a ton more questions differently, or nuke your account entirely and start over.


Posted by: Josh | Link to this comment | 02- 2-10 4:05 PM
horizontal rule
79

Well basically what I was thinking of is this. Suppose when you start out that each vertex as an attribute, depth, set to zero. Select some vertex to start with. Then do something like this:

def findcyclelen(v):
   ret = 0
   for each vertex w reachable from v:
      if w.depth:
         ret = max(ret,1 + v.depth - w.depth)
      else:
         w.depth = v.depth + 1
         ret = max(ret, findcyclelen(w))
   v.depth = 0
   return ret

or ... something.


Posted by: nosflow | Link to this comment | 02- 2-10 4:44 PM
horizontal rule
80

You're not going to get off that easy, nosflow, after making me think about this. If I understand what you're suggesting I think you'll end up needing to traverse some paths multiple times. How many times? How efficient? I have no idea.


Posted by: Eggplant | Link to this comment | 02- 2-10 4:56 PM
horizontal rule
81

I wrote 80 before I saw 79. With cycles, depth is not defined.


Posted by: Eggplant | Link to this comment | 02- 2-10 5:04 PM
horizontal rule
82

Yes, that's right—some paths get traversed more than once, in order to allow for the fact that some vertices are part of multiple cycles. (Setting the depth to zero after processing all the outgoing edges allows the right result in the latter cases at the cost of multiple traversals.) I'm not sure how many times—this is for sure not a particularly efficient algorithm—I conclude however that the point of Standpipe's comment way back when was simply that there are no particularly efficient algorithms.


Posted by: nosflow | Link to this comment | 02- 2-10 5:05 PM
horizontal rule
83

I wrote 80 before I saw 79. With cycles, depth is not defined.

So call the attribute "shmepth".


Posted by: nosflow | Link to this comment | 02- 2-10 5:06 PM
horizontal rule
84

(& castigate me for using the term confusingly at first, if you must.)


Posted by: nosflow | Link to this comment | 02- 2-10 5:06 PM
horizontal rule
85

Also "for each vertex w reachable from v" in 79 I mean each of v's neighbors.


Posted by: nosflow | Link to this comment | 02- 2-10 5:12 PM
horizontal rule
86

I'm confused. I think I'll have to execute this algorithm by hand on some examples to try to deconfuse myself.


Posted by: essear | Link to this comment | 02- 2-10 5:14 PM
horizontal rule
87

Then what keeps smepth from increasing without bound?


Posted by: Eggplant | Link to this comment | 02- 2-10 5:18 PM
horizontal rule
88

The sole graph on which I tested this has eight vertices with the following edges:

0 goes to 1, 2
1: 3
2: 4
3: 6
4: 5
5: 6, 7
6: 7
7: 5, 2

Then what keeps smepth from increasing without bound?

Smepth can only ever be between zero and the number of vertices minus one, because: in order for it to be a higher number, it would have to be the case that you were on a path that visited a vertex more than once. But in the course of constructing a given path vertices that are visited are assigned a nonzero smepth. If, while that path is being extended, a vertex that already has a nonzero smepth is encountered, that is (correctly!) treated as the beginning of a cycle, and the path ends there, we (possibly) update the length of the longest cycle, and go to the next unvisited-on-this-path-construction vertex.


Posted by: nosflow | Link to this comment | 02- 2-10 5:27 PM
horizontal rule
89

Isn't 87 a general problem with cyclic, um, smraphs?


Posted by: Sifu Tweety | Link to this comment | 02- 2-10 5:28 PM
horizontal rule
90

I want to know how many Hamilton-connected subgraphs there are. Get some epidemiologists on the horn, here.

Also in re: the talk of spectral clustering above, the use of that algorithm in this case seems to imply a certain sparseness of distal links, which given the userbase seems like a strong assumption.


Posted by: Sifu Tweety | Link to this comment | 02- 2-10 5:31 PM
horizontal rule
91

Unless the search defaults to "within 50 miles" or something, I guess, which seem likely.


Posted by: Sifu Tweety | Link to this comment | 02- 2-10 5:31 PM
horizontal rule
92

In particular taking the graph given in 88 (and labeling the vertices A-H for clarity, so it's (A -> B, C; B -> D; C -> E; D -> G; E -> F; F -> G, H; G -> H; H -> F, C)) and starting from A, you'd set B to 1, D to 2, G to 3, H to 4, F to 5, then when you're about to go from F back to G you would see that G had already been labeled with 3, and conclude that there was a cycle of length 1 + 5 - 3 = 3 vertices there, and when you were going from F back to H that H had been labeled with 4 and that there was a cycle of 1 + 5 - 4 = 2 vertices there; then set F back to 0, then go from H to C, setting it to 5, from C to E (6), E to F (7), and then you'd see a cycles of length 1 + 7 - 3 = 5 and 1 + 7 - 4 = 4, then unwinde all the way back to A and go from A to C, setting C to 1. (Then you would basically go back through this whole branch of the graph again—inefficient!)


Posted by: nosflow | Link to this comment | 02- 2-10 5:34 PM
horizontal rule
93

I've confirmed that neb's algorithm works when given a triangle. It only takes 50-odd steps to complete.


Posted by: essear | Link to this comment | 02- 2-10 5:34 PM
horizontal rule
94

The problem of finding the longest cycle in a directed graph is NP-complete: it includes the Hamilton cycle problem as a special case. So no-one knows an effective algorithm for it.

The reason why Ben's depth-first algorithm (which appears to be based on Dijkstra's shortest-path algorithm) doesn't work is that in the longest path, some vertices will not be visited according to their distance from the start: in particular half of them will be visited on the way back.


Posted by: Gareth Rees | Link to this comment | 02- 2-10 5:35 PM
horizontal rule
95

I've confirmed that neb's algorithm works when given a triangle. It only takes 50-odd steps to complete.

But, you know, processors are getting ever faster.


Posted by: nosflow | Link to this comment | 02- 2-10 5:36 PM
horizontal rule
96

The problem of finding the longest cycle in a directed graph is NP-complete: it includes the Hamilton cycle problem as a special case. So no-one knows an effective algorithm for it.

Aw man.


Posted by: nosflow | Link to this comment | 02- 2-10 5:38 PM
horizontal rule
97

it includes the Hamilton cycle problem as a special case.

Ha! That's obvious, now that you mention it. Clearly it's been too long since I learned the canonical examples of NP-complete problems.


Posted by: essear | Link to this comment | 02- 2-10 5:39 PM
horizontal rule
98

The problem of finding the longest cycle in a directed graph is NP-complete: it includes the Hamilton cycle problem as a special case. So no-one knows an effective algorithm for it.

Aha! I feel like this is the fact I would have presented, had I remembered it, assuming I ever knew it.


Posted by: Sifu Tweety | Link to this comment | 02- 2-10 5:39 PM
horizontal rule
99

What was Standpipe saying is O(n/log(n)), then?


Posted by: essear | Link to this comment | 02- 2-10 5:40 PM
horizontal rule
100

Keep going, nosflow! Maybe you can prove P=NP!


Posted by: essear | Link to this comment | 02- 2-10 5:40 PM
horizontal rule
101

There's a reason I brought up approximation algorithms.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 5:40 PM
horizontal rule
102

An approximation.

It's way long since I had anything to do with graphs.


Posted by: nosflow | Link to this comment | 02- 2-10 5:41 PM
horizontal rule
103

You take 100 back, essear. You know that I was laboring in ignorance.


Posted by: nosflow | Link to this comment | 02- 2-10 5:42 PM
horizontal rule
104

This.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 5:44 PM
horizontal rule
105

Get some epidemiologists on the horn, here.

Smraphylococcus is not a communicable disease.


Posted by: fake accent | Link to this comment | 02- 2-10 5:45 PM
horizontal rule
106

You take 100 back, essear. You know that I was laboring in ignorance.

As was I. I assume you feel approximately as stupid as I do, right now.

Probably I should, at some point in my life, have taken a comp sci class. Or kept sitting in on Babai's class for more than a week.


Posted by: essear | Link to this comment | 02- 2-10 5:46 PM
horizontal rule
107

Actually I probably feel more stupid than you do because:

(a) I actually did take Babai's classes on discrete math and algorithms
(b) Earlier today I read the description of the hamiltonian cycle problem but it didn't occur to me that to answer "what's the length of the longest cycle?" is also to answer "is the length of the longest cycle equal to the number of vertices?".
(c) Gareth says the algorithm above doesn't work but I still don't understand why.

On the other hand, there are mitigating factors:

(a) I generally feel pretty smart to start off with so I might still feel smarter than you do even after the above facts are taken into account
(b) IIRC you're some kind of scientician whereas I'm a lowly humanist.


Posted by: nosflow | Link to this comment | 02- 2-10 5:52 PM
horizontal rule
108

Or kept sitting in on Babai's class for more than a week.

Sounds like you passed up a rare opportunity:

Babai the Great (c.551-628) was an early church father, who set some of the foundational pillars of the Assyrian Church of the East.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 5:52 PM
horizontal rule
109

My policy is never to include a period after the first element of a list, but always to do so after the next elements.


Posted by: nosflow | Link to this comment | 02- 2-10 5:53 PM
horizontal rule
110

OT Meanwhile Dave Noon is blaspheming and showing his ethnic prejudices against my native culture. Good vodka, preferably from potatoes, drunk neat and freezing cold, is a wonderful thing and a great complement to many foods.


Posted by: teraz kurwa my | Link to this comment | 02- 2-10 5:54 PM
horizontal rule
111

Or kept sitting in on Babai's class for more than a week

I sat in on that class all quarter. Did the homework, took the tests, and even received a grade for it. (One might even say I "registered" for it.) Believe it or not, 8 years later, this information wasn't at my fingertips either.


Posted by: Otto von Bisquick | Link to this comment | 02- 2-10 5:55 PM
horizontal rule
112

I know it's wrong of me, but I'm having trouble reading about Babai the Great without laughing at many of the names in the article.


Posted by: fake accent | Link to this comment | 02- 2-10 5:55 PM
horizontal rule
113

(Though I did retain enough intuition that I had a strong suspicion that there was no efficient algorithm to solve this problem.)


Posted by: Otto von Bisquick | Link to this comment | 02- 2-10 5:56 PM
horizontal rule
114

Babai teaches more than one class, Otto.


Posted by: nosflow | Link to this comment | 02- 2-10 5:56 PM
horizontal rule
115

I forget the name of the one I sat in on for a week. Something like "Introduction to all those aspects of mathematics that essear has been wrongfully ignoring in favor of taking more topology classes than he will ever need, much less remember a year from now".


Posted by: essear | Link to this comment | 02- 2-10 5:59 PM
horizontal rule
116

That's CS374, I think, in the numbering that was in use back when I didn't take it.


Posted by: nosflow | Link to this comment | 02- 2-10 6:01 PM
horizontal rule
117

114: Really? Is that why I remember taking two classes from him?


Posted by: Otto von Bisquick | Link to this comment | 02- 2-10 6:01 PM
horizontal rule
118

Standpipe was referring to Alon, Yuster and Zwick (1995), "Color-coding" (but linked to a David Eppstein presentation instead, not sure why).

AYZ give an algorithm that finds a cycle of length k in time 2O(k)·|E| log |V|, so it can find a cycle of length Θ(log |V|) in polynomial time. Since the longest cycle may have length |V|, this gives us a polynomial approximation algorithm that gets within a factor of Ο(|V| / log |V|) of the true result.

(This is the O(n / log n) that Standpipe quoted from the Eppstein presentation.)


Posted by: Gareth Rees | Link to this comment | 02- 2-10 6:03 PM
horizontal rule
119

In my day, there was Discrete Math, there was Algorithms, and then there was Honors Combinatorics and Probability. 2001-2002.


Posted by: Otto von Bisquick | Link to this comment | 02- 2-10 6:03 PM
horizontal rule
120

I don't know, Otto. I was just confused by your reference to "that class" in 111, as if the class that essear sat in on had to be the one that you took, in virtue of there being only one Babai-led class. Indeed, even your having taken two classes from him doesn't guarantee this result, especially since he is known to me to allow people to take his advanced combinatorics class without having taken either of his two more introductory classes. (I know this because one quarter my first year I wanted to take some class or other but couldn't for some reason or other and the CS department person I was asking about this suggested Babai's (advanced) class instead, and when I balked he basically said "but it's easy, I mean, you can count, right?".)


Posted by: nosflow | Link to this comment | 02- 2-10 6:03 PM
horizontal rule
121

but linked to a David Eppstein presentation instead, not sure why

I went looking for approximation results for the problem in question and found them listed conveniently in his slides. I linked to the AYZ paper in 104.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 6:05 PM
horizontal rule
122

this gives us a polynomial approximation algorithm that gets within a factor of Ο(|V| / log |V|) of the true result.

Is that useful? log|V| is a hell of a lot smaller than |V|, so this doesn't seem like it's in the ballpark.


Posted by: essear | Link to this comment | 02- 2-10 6:08 PM
horizontal rule
123

No doubt its usefulness or uselessness depends on what you want the information for in the first place.


Posted by: nosflow | Link to this comment | 02- 2-10 6:11 PM
horizontal rule
124

You might think that 123 is completely uninformative, but to that I say, it depends on what you want to be informed about.


Posted by: nosflow | Link to this comment | 02- 2-10 6:13 PM
horizontal rule
125

120: OK, I give. There is no guarantee that the class to which essear was referring was one of the two classes that I took from Babai. I figured it was a safe assumption that the briefly audited class was one of the two classes I took from Babai, as both of those classes covered a fair amount of material that is germane to this discussion. It is completely true, however, that this fact does not imply that the third Babai course for undergraduates—which I did not take—did not cover some similar material (or, in fact, some material that would be even.more applicable to the problem under discussion). Ergo, it is completely possible that I did not take the course that essear professes to have sat in on for a week.

I regret any misunderstandings that my careless commenting may have caused, and henceforth abjure my wicked ways.


Posted by: Otto von Bisquick | Link to this comment | 02- 2-10 6:14 PM
horizontal rule
126

the two classes that I took from Babai ... the two classes that I took from Babai

Oof. I'm just trying to make breadthfirst feel comfortable here, I guess.


Posted by: Otto von Bisquick | Link to this comment | 02- 2-10 6:19 PM
horizontal rule
127

The two classes that I took from Babai.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 6:20 PM
horizontal rule
128

I cannot believe you guys managed to turn a perfectly interesting potential dating thread into a math/comp sci thread. Boo hiss!


Posted by: Witt | Link to this comment | 02- 2-10 6:20 PM
horizontal rule
129

Maroon fight!


Posted by: fake accent | Link to this comment | 02- 2-10 6:21 PM
horizontal rule
130

128: It's OKCupid. The people who run the site did most of that work already; everyone here is just following their lead.


Posted by: Josh | Link to this comment | 02- 2-10 6:22 PM
horizontal rule
131

128: Well, nosflow kind of stacked the deck with the OP the wrote.


Posted by: Otto von Bisquick | Link to this comment | 02- 2-10 6:22 PM
horizontal rule
132

the two classes that I took from Babai

Give Babai back his classes!

I think the one I went to for a few days was actually the combinatorics one, so maybe unrelated to this thread. But, I don't really know what it covered, because I didn't go for long. Counting is way too difficult, anyway.


Posted by: essear | Link to this comment | 02- 2-10 6:23 PM
horizontal rule
133

his ethnic prejudices against my native culture.

Meden agan. I knew a bloke (English, name of Kowa/sk1) who married a Polish woman. He happily accepted that vodka was regarded as a universal complement and a miracle cure. But he resented it when he took to his bed for a day to protect his liver against the alcoholic onslaught, only for his brother in law to press vodka on him because he was feeling a bit rough.


Posted by: OFE | Link to this comment | 02- 2-10 6:23 PM
horizontal rule
134

the OP the wrote

Fuck. Time for me to get away from the computer. Maybe I'll go take two more classes from Babai.


Posted by: Otto von Bisquick | Link to this comment | 02- 2-10 6:24 PM
horizontal rule
135

The statistic I want to see is how many people on OkCupid get the names of their favorite books and movies wrong. It's full of "I love Two Kill the Mockingbird!"


Posted by: essear | Link to this comment | 02- 2-10 6:27 PM
horizontal rule
136

"Two Kill the Mockingbird!" is AOTW a google orphan.


Posted by: fake accent | Link to this comment | 02- 2-10 6:30 PM
horizontal rule
137

No, no, essear, the canonical mistitling is How to Kill a Mockingbird.


Posted by: Witt | Link to this comment | 02- 2-10 6:31 PM
horizontal rule
138

Sad. I was hoping for Tequila Monkey-Bard.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 6:32 PM
horizontal rule
139

I personally am delighted that an interesting graph theory thread remained on target despite the ever-present danger it could have turned into a dating thread.

135: I'm a huge fan of Gravity's Rainblow.

In third news, I'm impressed with nosflow's resiliency; he managed to deflect conversation onto an irrelevancy and regain a sense of intellectual superiority in like three comments. Can't keep him down!


Posted by: Sifu Tweety | Link to this comment | 02- 2-10 6:32 PM
horizontal rule
140

O muse, sing of the monkeys, and, um, the monkeys, 'cause monkeys, yeah. *passes out*


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 6:33 PM
horizontal rule
141

You know what book totally turns girls on? War and Peas.


Posted by: Sifu Tweety | Link to this comment | 02- 2-10 6:34 PM
horizontal rule
142

At Swim Two Ways of Looking at a Mockingbird


Posted by: fake accent | Link to this comment | 02- 2-10 6:35 PM
horizontal rule
143

138 is making me laugh.


Posted by: Witt | Link to this comment | 02- 2-10 6:37 PM
horizontal rule
144

||

Things Facebook tells me that I don't need to know: some postdoc I know is leaving 'omg your butt is so hott n sexy' comments on the Facebook photos of some woman who likes to post lots of pictures of herself in thongs.

|>


Posted by: essear | Link to this comment | 02- 2-10 7:21 PM
horizontal rule
145

Jealousy is unbecoming, essear.


Posted by: Standpipe Bridgeplate | Link to this comment | 02- 2-10 7:30 PM
horizontal rule
146

144: Your post-doc acquaintance apparently hasn't been reading the findings of the OKcupid datamongers (see rule #2)


Posted by: Knecht Ruprecht | Link to this comment | 02- 2-10 7:33 PM
horizontal rule
147

144: I think it's too soon to judge. What's his or her field?


Posted by: Sifu Tweety | Link to this comment | 02- 2-10 7:37 PM
horizontal rule
148

If facebook is telling you it, it must be what you need to know.


Posted by: fake accent | Link to this comment | 02- 2-10 7:40 PM
horizontal rule
149

148: I had a weird experience with this. Recently, friends invited me to a concert of a band I had never heard of (in person, not over email, I did not google the band); not 6 hours later I was being told by Facebook ads that I should go see them.


Posted by: Parenthetical | Link to this comment | 02- 2-10 7:43 PM
horizontal rule
150

None of my Facebook friends post pictures of themselves in thongs. I'm not sure whether to be smug or jealous.


Posted by: emdash | Link to this comment | 02- 2-10 7:46 PM
horizontal rule
151

149: Where did your friends hear about the band?


Posted by: fake accent | Link to this comment | 02- 2-10 7:51 PM
horizontal rule
152

150:

Wierd. A friend just posted a thong pic.

(For what it is worth, it wasnt Carp or Di.)


Posted by: Will | Link to this comment | 02- 2-10 7:52 PM
horizontal rule
153

not 6 hours later I was being told by Facebook ads that I should go see them.

I get endless amusement out of the choice of context-sensitive ads that gmail serves up for me. The algorithm was demonstrably so good at detecting purchase occasions for various goods and services, I decided to go for broke and write, "You know what I'd like right now? A big baggie of really good marijuana."

My correspondent predicted that this would trigger ads for drug addiction programs, and sure enough, that's exactly what I got.

Get crackin', google developer teams!


Posted by: KR | Link to this comment | 02- 2-10 7:53 PM
horizontal rule
154

I could not tell you a single ad that gmail has shown me. I know I must have seen them advertising something. I have gmail open in another tab right now and can't say what they're advertising. I do remember seeing maps of locations in the sidebar when addresses were mentioned.


Posted by: fake accent | Link to this comment | 02- 2-10 7:58 PM
horizontal rule
155

152: Not a member of the private flickr group "appellate briefs", I take it?


Posted by: KR | Link to this comment | 02- 2-10 7:59 PM
horizontal rule
156

151: Not Facebook - she's not a member.


Posted by: Parenthetical | Link to this comment | 02- 2-10 8:01 PM
horizontal rule
157

Maroon fight!

That's pretty weak, fake accent.

I find it hilarious when people misspell the names of their supposed favorites, but I can't recall any particularly telling examples, unfortunately.


Posted by: nosflow | Link to this comment | 02- 2-10 8:03 PM
horizontal rule
158

The other day, a FB friend befriended someone from here. The party of the second part has a very distinctive name. The crossing of streams felt weird.


Posted by: md 20/400 | Link to this comment | 02- 2-10 8:04 PM
horizontal rule
159

Maybe I'll go take two more classes from Babai.

Do that, and call me in the morning.


Posted by: nosflow | Link to this comment | 02- 2-10 8:08 PM
horizontal rule
160

158: I had a similar experience a week or so ago, except it was a comment rather than a friending and I'm not FB friends with the recipient (whom I know only from here (and elsewhere on the interwebs)).


Posted by: Not Prince Hamlet | Link to this comment | 02- 2-10 8:14 PM
horizontal rule
161

I find it hilarious when people misspell the names of their supposed favorites, but I can't recall any particularly telling examples, unfortunately.

Not misspelling, exactly, but...

1. Former FLOTUS Barbara Bush, responding to a question about her favorite novel, saying she loved all the novels of Emily Brontë.

2. The late Michael Jackson saying he had read the works of Socrates.


Posted by: Knecht Ruprecht | Link to this comment | 02- 2-10 8:19 PM
horizontal rule
162

Relevant. Via k-sky, on Facebook.


Posted by: teofilo | Link to this comment | 02- 2-10 8:32 PM
horizontal rule
163

Discussed in a thread below. Also, kind of stupid.


Posted by: nosflow | Link to this comment | 02- 2-10 8:33 PM
horizontal rule
164

Also, kind of stupid.

Rather.


Posted by: Sifu Tweety | Link to this comment | 02- 2-10 8:34 PM
horizontal rule
165

Discussed in a thread below.

I was concerned about this possibility. Obviously, I have not been reading most of the recent threads.


Posted by: teofilo | Link to this comment | 02- 2-10 8:36 PM
horizontal rule
166

Carry on.


Posted by: teofilo | Link to this comment | 02- 2-10 8:36 PM
horizontal rule
167

Geez, noseflow, you're the one who transformed this thread into a replicant of that thread, and now you revel in the confusion of others.


Posted by: Cryptic ned | Link to this comment | 02- 2-10 8:36 PM
horizontal rule
168

Neb, you might want to check the thread for things that are not written backward.


Posted by: Moby Hick | Link to this comment | 02- 2-10 10:11 PM
horizontal rule
169

||

As if anybody cares, neb has screwed up his HTML in the main post in some obscure way such that it renders fine in Firefox, but in IE7 the whole of the front page is italicised after "Suppose you had a directed graph whose vertices are users with an edge from v1 to v2".

|>


Posted by: OFE | Link to this comment | 02- 3-10 4:06 AM
horizontal rule
170

39: This is me consciously not rising to the bait, because I can exert self-control. Yes.

Actually, there's a lot of interesting work going on these days in "community discovery", using weaker notions of parts-of-the-network than connected components. There turn out to be connections between these and spectral clustering. (I was very annoyed with myself when Mark wrote that paper, because I'd vaguely thought of looking for a link, and then of course never did anything with it.) It might be interesting to look for block models in dating or contact graphs.

Also: Diffusion maps.

And now, coffee and teaching.


Posted by: Cosma Shalizi | Link to this comment | 02- 3-10 6:48 AM
horizontal rule
171

On the topic of OKCupid, let me just say that browsing through the profiles for very long makes me despair for my species.


Posted by: Populuxe | Link to this comment | 02- 3-10 7:33 AM
horizontal rule
172

The link in 162 leads, after a little poking around, to Texts From Last Night, which absolutely has to have been linked here at some point. This is my first exposure to it. Some very funny stuff there.


Posted by: togolosh | Link to this comment | 02- 3-10 7:42 AM
horizontal rule
173

Further to 172, a sample:

(518): alright so where did all these fingerpaintings on my bedroom wall come from?
(1-518): dude. you drew those with your dick


Posted by: togolosh | Link to this comment | 02- 3-10 7:46 AM
horizontal rule