Complex network analysis (CNA), a subset of graph theory, is an emerging approach to the analysis of functional connectivity in the brain, allowing quantitative assessment of network properties such as functional segregation, integration, resilience, and centrality. Here, we show how a classification framework complements complex network analysis by providing an efficient and objective means of selecting the best network model characterizing given functional connectivity data. We describe a novel kernel-sum learning approach, block diagonal optimization (BDopt), which can be applied to CNA features to single out graph-theoretic characteristics and/or anatomical regions of interest underlying discrimination, while mitigating problems of multiple comparisons. As a proof of concept for the method's applicability to future neurodiagnostics, we apply BDopt classification to two resting state fMRI data sets: a trait (between-subjects) classification of patients with schizophrenia vs. controls, and a state (within-subjects) classification of wake vs. sleep, demonstrating powerful discriminant accuracy for the proposed framework.