Let's say you have databases $A$ and $B$, and a population of users $\left\{u_1,\ldots,u_n\right\}$. You're building a social network graph of $\left\{u_1,\ldots,u_n\right\}$. From database A, you get an edge weight feature $a(i,j)$ which connects user $i$ to user $j$. From database B, you get a similar edge weight $b(i,j)$.

You want to build a single network incorporating all this data. I can think of a couple ways to do this.

  1. Treat edges $a$ and $b$ separately, make a multigraph...

  2. Combine the two edge weights together in some way. Suppose you define the edge weights $e(i,j) = a(i,j) + \alpha b(i,j)$, and $\alpha$ is a parameter.

I'm mostly interested in method $2$, but allow for the possibility that $1$ could work well. Is there a way to optimize the choice of $\alpha$? One idea would be: remove a small subset of the edges, and then try to predict where they would be (using a clustering/triangle approach, say), or fitting a likelihood value to where the removed edges are.


No, you can't do it in an unsupervised way. The reason is simple: somehow you need to incorporate a rule of when two nodes should be connected; or if the final graph is weighted, you need a rule about the weights you expect given the $a(i,j)$ and $b(i,j)$. In the first case you end up doing classification, in the later regression. The missing rule is the free parameter you try to find, that is how $a$ and $b$ are related.

If you can't make an arbitrary decision for the free parameter (e.g. just take their sum, that is free parameter equals to one), then you need to build a dataset with several different combinations of $a$ and $b$, the required result in each case and find the free parameter using a supervised approach. By the way, I don't know your data, but you already made some assumption about that rule: that it connects $a$ and $b$ in a linear way.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the answer. I guess unsupervised isn't really the right way to describe what I'm looking for. I guess I'm looking for a generative model. For example, I randomly remove a small amount of edges from the network, and then try to predict where those edges should be (or how much weight they'd have). Or I have some MLE method. Will clarify my question a little bit. $\endgroup$ – quasi Jan 15 '14 at 19:23
  • $\begingroup$ Check out this paper: It is more or less close to what you try to do and it uses GLM to predict edges. Also to avoid building manually the ground truth for the final network, they rely on external sources. Might be useful. $\endgroup$ – iliasfl Jan 16 '14 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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