Community finding algorithms in large heterogeneous networks 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?
 A: 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):

*

*Murata'10

*Ghosh'11

*Papadopoulos'11
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.
