Consider a network that consists of vertices with various meanings. For example: stack overflow users, keywords and user location when asking/answering a question. In this network, when a user asks a question its ID node is linked to several keyword vertices and to a vertex representing users' geographical location.

I would like to ask a general and vague question: are there any meaningful communities in this network? One approach would be to link (lets say) users using other vertices and then analyzing the resulting graph of users. However, are there approaches that retain the heterogeneous types of information in the graph? Are there metric measurements that take into consideration various types of nodes?


The first graph you describe here is a tripartite graph, which means it has three types of nodes, and links only between nodes of different types. The second graph you describe, containing only user nodes, is the result of the so-called projection over the user dimension. However, performing such an operation results in a loss of information, because several multipartite graphs can lead to the same projection (as shown in Guillaume'06 for bipartite graphs). So, it is better to directly detect communities in the original graph.

However, certain questions arise if you want to do so. The most important is: what is a community for you? A group of nodes of any type, or a group of same-type nodes? Depending on this, you can apply various methods. A lot of them were developped to handle folksonomy graphs, in which the three types of nodes respectively represent users, annotations and shared resources (the users associated annotations to resources). But they can be applied to networks representing other systems, such as yours.

Here're some community detection algorithms designed for tripartite graphs (the list is obviously not complete):

However, I don't think any implementation is freely available, if that's what you're looking for. Also, note there's a generalized version of the modularity (see Murata'10), defined for tripartite network. The modularity is a metric measuring the "quality" of a community structure. Many community detection methods are based on the optimization of this metric. If you want to program your own tool, implementing this modularity and then applying a classic optimization method might be the easiest way.

  • $\begingroup$ Thank you. You gave the precise information that I needed: set of of correct terms to search for and list of works to seed my searches. As to your question "what is a community for you" - you are right. Like in many other fields "what you are looking for" is the most important, but not the most clear question. In my case I start exploring a graph and hope finding insights that will help me answer this question. $\endgroup$ – David D Nov 5 '13 at 12:34
  • $\begingroup$ Glad to help. An additional precision, regarding terminology: you can actually find people calling this type of network "heterogenous" in the literature, but the term is not only used for multipartite graphs. Sometimes, it just means there are different types of nodes, without implying any constraint on the way they are connected. I've also seen it used to name multiplex graphs (graphs with different types of links). By the way, if you find any implementation, it'd be nice if you could post it here, it can be a useful thing to know. cheers! $\endgroup$ – Vincent Labatut Nov 5 '13 at 16:22

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.