Community detection (graph clustering) of a weighted graph with node attribute (categorical or quantitative)

Consider a weighted graph having node attributes. Say the nodes are birds and the attribute could be either categorical (gender) or quantitative (number of feathers), i.e. similarly to this example.

One answer of this question already explained how to do community detection/graph clustering on a weighted graph with igraph in R, which is great.

However, how would one proceed to do the same but taking into account node attributes (i.e. having nodes with similar attributes grouped together, in addition of taking into account their weighted edges), in the case when:

• each node's attribute is categorical (e.g. bird's gender)
• each node's attribute is quantitative (e.g. bird's number of feathers)
• each node has several attributes (which could be categorical or quantitative)

Having an answer to any of this case with an available package (in python or R) would already be fantastic.

If it makes any difference, the kind of data i actually have is a network very close to a grid ("lattice") network. And I am trying to get non-overlapping communities in this grid. In terms of numbers, I have maybe 10000 nodes that I would like to partition into 100 to 1000 communities. Each node is connected to 4 adjacent node (grid/lattice pattern).

• My guess is that you would incorporate the node attributes into the weights. For categorical attributes adjust the weights based on equality. For continuous attributes, adjust the weights based on a difference measure. – xan Aug 13 '15 at 18:48
• Thanks @xan this is an interesting idea, I will seriously consider it. Meanwhile if I could find an existing algorithm (supported by graph theory) already implemented in some R or python package that would be ideal – michael Aug 14 '15 at 1:35

And your final edge weight will be something like: $$e_{new\;weight} = (w_1\ast j_1+w_2\ast n_2+...+w_k\ast n_k)\ast e_{old\;weight}$$