Community Detection in Networks with Node Features

1 The joint community detection criterion

• JCDC adds feature-based edge weights to an assortative criterion, aiming to strengthen within-community connections relative to between-community connections.The starting criterion is a simple analogue of modularity and is maximized over community label assignments.Source: §1 · p. 2
• Community-specific coefficients βk let JCDC learn which features matter for each community, while wn controls the balance between network and feature information.The criterion is maximized over both labels e and feature coefficients β.Source: §1 · p. 2
• Feature similarities φij are chosen for the feature type, standardized by dimension, and passed through an increasing, concave weight function.Other functions with a similar shape, including the logit exponential, were reported to perform similarly.Source: §1 · pp. 2–3

2 Estimation

• Block coordinate descent alternates between optimizing labels with fixed feature parameters and optimizing parameters with fixed labels until convergence.Searching all possible label assignments is infeasible, so the label step uses tabu search with one-node-at-a-time switching.Source: §2 · p. 3, §2.1 · p. 3

2.1 Optimizing over label assignments with fixed weights

• A local label update compares a node’s weighted connections to candidate communities; α = 1 compares average weights, while α below or above 1 favors larger or smaller communities, respectively.The update avoids recalculating the entire criterion; wn controls the maximum feature-driven edge reweighting, with larger wn making network structure more dominant.Source: §2.1 · p. 3

2.2 Optimizing over weights with fixed label assignments

• For fixed labels, concavity makes the criterion straightforward to optimize over each βk by gradient ascent; βk controls the impact of features on its community.A small L1 penalty is used to guard against numerically unstable parameter solutions.Source: §2.2 · p. 4

3 Consistency

• JCDC is asymptotically consistent when the network follows a stochastic block model and features are independently generated from a uniformly bounded distribution, subject to regularity conditions.The theorem additionally requires conditions on feature similarities and coefficients, nonvanishing communities, assortativity, and growth of nρn and wnρn.Source: §3 · p. 4
• The regularity conditions require communities not to vanish asymptotically and enforce assortativity; bounded feature similarities are also required.The paper suggests standardizing node features and discarding very low-variance features for numerical stability.Source: §3 · p. 4
• Agreement between estimated and true labels is measured after minimizing label mismatch over permutations of community labels.Community labels are defined only up to an arbitrary permutation.Source: §3 · p. 4

4 Simulation studies

• The experiment uses 150 nodes and two communities, varies r from 0.25 to 0.75 and µ from 0.5 to 2, and averages NMI over 30 replications.The comparison includes joint, network-only, and feature-only methods.Source: §4 · p. 5
• Across r and µ, JCDC leverages network and feature information, deteriorating only when neither is informative; informative features help more at larger wn, while noise has a slightly greater but weak effect at lower wn.The heatmaps report average NMI across the different methods as r and µ vary.Source: Figure 1 · p. 5, §4 · p. 5
• CESNA and BAGC perform worse overall in these simulations; spectral clustering depends on r, while K-means depends on µ.BAGC often groups all hub nodes into one community.Source: §4 · p. 5

5.1 The world trade network

• JCDC attains the highest continent NMI; CASC performs similarly to spectral clustering, while CESNA and BAGC fail to recover the continent partition.No method estimates Africa well, likely because its trade is disassortative; JCDC estimates North America, South America, and Asia accurately but splits Europe.Source: Figure 2 · p. 6, §5.1 · p. 6
• 1980 world position most influences connections formed by Asian countries, whereas 1994 world position matters most in Europe.Source: §5.1 · p. 7, Table 1 · p. 7

5.2 The lawyer friendship network

• JCDC obtains the highest status NMI, with w_n=5 performing slightly better than w_n=1.5; spectral clustering and K-means have equal, reasonably high NMI.CASC improves on spectral clustering, with NMI slightly below JCDC at w_n=1.5.Source: §5.2 · p. 7
• Office location, years with the firm, and age correlate most with status structure for both partners and associates; gender influence is uncertain given the small number of women.Source: §5.2 · p. 7, Table 2 · p. 7

• Feature-based weights and community-specific coefficients can improve detection over network-only or feature-only clustering when feature and network cluster structures are related.The coefficients help identify features correlated with community structure and guard against noise features.Source: §6 · p. 7
• The criterion targets assortative communities, where within-community connections are more frequent than between-community connections, and benefits most from similarly clustered features.Source: §6 · p. 8
• Extensions include jointly accounting for degree variation correlated with features, overlapping communities, and more involved or data-specific models for real networks.The authors report that standard generative models they tried did not compete empirically with non-model-based JCDC on real data.Source: §6 · p. 8

A.1 Choice of tuning parameters

• The α experiment uses 120-node, two-community stochastic block models, varies community imbalance, and averages results over 50 replications.Features are held constant because α is unrelated to feature weights.Source: §A.1 · p. 9
• For balanced communities, JCDC produces balanced estimates and outperforms spectral clustering in NMI across α; more generally, larger α favors balanced estimates, and the accuracy-advantage range depends on imbalance.The study reports the larger estimated community size and NMI across α; α = 1 is used in the main analyses, though users can change it when community-size information is available.Source: Figure 4 · p. 9, §A.1 · p. 9
• As wn increases, estimated communities become closer to the network partition; smaller wn gives more influence to features and better agreement with the feature partition than with the network partition.The comparison uses two community partitions and reports NMI between estimates and each partition.Source: Figure 5 · p. 10, §A.1 · p. 10

A.2 Proofs

• The concentration argument requires conditions 1 and 2, wnρn → ∞, and 0 < α ≤ 2, and uses a parameter net and union bounds.The proof bounds the difference between R and R0 and then takes a union bound over community assignments.Source: §A.2 · pp. 11–12
• The proof represents assignments by U, a confusion matrix between estimated and true communities, with U = DO corresponding to perfect estimation up to label permutation.The estimator maximizes R over the labels e and parameters β; the argument assumes A and F are conditionally independent given c.Source: §A.2 · pp. 10–12
• Under condition 3 and the stated interval for α, the population criterion g(U) is uniquely maximized when U = DO for a permutation matrix O.This identifies the population optimum with the true communities up to label permutation.Source: §A.2 · p. 13
• As the score tolerance xn tends to zero, the worst label distance yn also tends to zero; the proof applies this implication under the theorem’s assumption.Distance is measured from U to the set of permutation-equivalent perfect assignments.Source: §A.2 · p. 14