I think there would almost certainly be one enormous class, and a handful of two-person "new member contacts new member" classes.
So you may continue living your life now. You're welcome.
I offer this as a stop-gap; it's re-drawn from the data in here, but only looking at the largest connected component.
Oh, and a larger number of singleton classes.
4: Those are actual mutual relationships. The graph of prospects and hopefuls will be much different.
I like it that the entire front page is in italics now, but I think the comments should be too. Possibly bold italics.
Will this explain why so many polyamorous people on OkCupid are apparently interested in me?
9: Maybe you just clique with people?
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.
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?
I don't have a clue what Ben is asking in the second paragraph of the original post.
I don't have a clue what Ben is asking in the second paragraph of the original post.
To answer my own question: Yes.
Best known approximation for … digraphs: O(n / log n) [Alon, Yuster & Zwick 1995]
12: I would suggest a depth-first search.
Breadth-first, actually.
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.
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.
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.)
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.
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.
24: Or 2a -- polyamorous people on OkCupid contact more people than the regular amorous people.
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.
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.
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.
than single people. Jesus, I need a nap.
28: I have no specific insights on OkCupid or polyamorous people. I just like categorizations that are exhaustive.
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!
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.
Good choice by BioMedCentral for the very first article in the first issue of their new "Women's Health" journal.
Yes, but Donna isn't speaking to Barbara because of what happened at the Olive Garden last July.
24: You left out another possibility: (4) people looking to cheat who claim to be polyamorous.
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.
35: I don't see how that would apply to reasons for contacting CB. Also, AWB mentioned that in 26.
Most of these people have links to their respective polyamours' own OkCupid profiles, so they're either legit or impressively conspiratorial.
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.)
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.
Sorry I rejected you, Natilo, but I had to do it. I'm a jerk.
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.
42: Not that I meant to suggest CB was especially attractive to the less-picky.
44: Yes, I'm going back to the other thread. 42 came out poorly.
It's OK. By "less picky" I just assumed he meant "less likely to be intimidated by the overwhelmingly awesome."
(OK, I admit it, I'm just hoping to provoke more commenting from Cosma.)
I wish this ever worked.
All these years, and it's still fucking hilarious that the famous sex researchers are Masters and Johnson. Shame that Dr. Bristols was unavailable.
Would you be amused to learn that the modern procedure for the vasectomy was invented by Dr. Blanc?
(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.
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.
the output of the Shi-Malik algorithm
The stuff that Google turns up for this looks pretty interesting.
normalized cuts allow you to segment the graph into richly interconnected subgraphs
This sounds thrillingly sensual.
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.
There's more: Random walks! Piecewise constant eigenfunctions! Okay, these aren't as sensual.
All the world's a graph, and we are merely richly interconnected subgraphs.
54: Yeah, like pagerank, it has a bit of that forehead slapping effect.
Likes: random walks on the beach, piecewise constant eignenunctions at sunset.
eignenunctions
Mathematicians get these just before they die.
62: If you wouldn't have said anything, I would have assumed you were amending 60, not being pwned.
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".
If you wouldn't have said anything
You just gave me an aneurysm.
along the lines of that one late-night discussion of Indians and boatbuilding and Pacific Islanders and whatnot
By which I mean this.
Was the reason because of the grammaticalness?
67: Is "If you would have said nothing" that much better?
For you homework tonight, Bave, compute the eigenunctions of the co-redemptrix.
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.
So are we closer now than ever before to answering the angels and pin question?
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?
If not, perhaps you might wish to consider explaining what you were thinking of at greater length.
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.
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.
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.
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.
I wrote 80 before I saw 79. With cycles, depth is not defined.
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.
I wrote 80 before I saw 79. With cycles, depth is not defined.
So call the attribute "shmepth".
(& castigate me for using the term confusingly at first, if you must.)
Also "for each vertex w reachable from v" in 79 I mean each of v's neighbors.
I'm confused. I think I'll have to execute this algorithm by hand on some examples to try to deconfuse myself.
Then what keeps smepth from increasing without bound?
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.
Isn't 87 a general problem with cyclic, um, smraphs?
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.
Unless the search defaults to "within 50 miles" or something, I guess, which seem likely.
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!)
I've confirmed that neb's algorithm works when given a triangle. It only takes 50-odd steps to complete.
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.
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.
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.
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.
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.
What was Standpipe saying is O(n/log(n)), then?
Keep going, nosflow! Maybe you can prove P=NP!
There's a reason I brought up approximation algorithms.
An approximation.
It's way long since I had anything to do with graphs.
You take 100 back, essear. You know that I was laboring in ignorance.
Get some epidemiologists on the horn, here.
Smraphylococcus is not a communicable disease.
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.
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.
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.
My policy is never to include a period after the first element of a list, but always to do so after the next elements.
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.
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.
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.
(Though I did retain enough intuition that I had a strong suspicion that there was no efficient algorithm to solve this problem.)
Babai teaches more than one class, Otto.
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".
That's CS374, I think, in the numbering that was in use back when I didn't take it.
114: Really? Is that why I remember taking two classes from him?
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.)
In my day, there was Discrete Math, there was Algorithms, and then there was Honors Combinatorics and Probability. 2001-2002.
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?".)
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.
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.
No doubt its usefulness or uselessness depends on what you want the information for in the first place.
You might think that 123 is completely uninformative, but to that I say, it depends on what you want to be informed about.
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.
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.
The two classes that I took from Babai.
I cannot believe you guys managed to turn a perfectly interesting potential dating thread into a math/comp sci thread. Boo hiss!
128: It's OKCupid. The people who run the site did most of that work already; everyone here is just following their lead.
128: Well, nosflow kind of stacked the deck with the OP the wrote.
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.
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.
the OP the wrote
Fuck. Time for me to get away from the computer. Maybe I'll go take two more classes from Babai.
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!"
"Two Kill the Mockingbird!" is AOTW a google orphan.
No, no, essear, the canonical mistitling is How to Kill a Mockingbird.
Sad. I was hoping for Tequila Monkey-Bard.
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!
O muse, sing of the monkeys, and, um, the monkeys, 'cause monkeys, yeah. *passes out*
You know what book totally turns girls on? War and Peas.
At Swim Two Ways of Looking at a Mockingbird
||
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.
|>
Jealousy is unbecoming, essear.
144: I think it's too soon to judge. What's his or her field?
If facebook is telling you it, it must be what you need to know.
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.
None of my Facebook friends post pictures of themselves in thongs. I'm not sure whether to be smug or jealous.
149: Where did your friends hear about the band?
150:
Wierd. A friend just posted a thong pic.
(For what it is worth, it wasnt Carp or Di.)
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.
151: Not Facebook - she's not a member.
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.
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.
Maybe I'll go take two more classes from Babai.
Do that, and call me in the morning.
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)).
Discussed in a thread below. Also, kind of stupid.
Discussed in a thread below.
I was concerned about this possibility. Obviously, I have not been reading most of the recent threads.
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.
Neb, you might want to check the thread for things that are not written backward.
||
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".
|>
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.
On the topic of OKCupid, let me just say that browsing through the profiles for very long makes me despair for my species.
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.
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
