Computer Science ›› 2018, Vol. 45 ›› Issue (7): 293-298.doi: 10.11896/j.issn.1002-137X.2018.07.050

• Interdiscipline & Frontier • Previous Articles     Next Articles

Multi-feature Fusion Classification Method Based on High-order Minimum Spanning Tree Brain Network

QIN Meng-na, CHEN Jun-jie, GUO Hao   

  1. College of Computer Science and Technology,Taiyuan University of Technology,Jinzhong,Shanxi 030600,China
  • Received:2017-06-02 Online:2018-07-30 Published:2018-07-30

Abstract: Existing researches on classification of brain diseases is based on the traditional low-order functional connectivity network.Low-order functional connectivity network may overlook the complex and dynamic interaction patterns among brain regions,which are essentially time-varying.The high-order functional connectivity network can reflect the abundant dynamic time information contained in the network.However,the traditional high-order functional connectivity network adopts the clustering method to reduce the dimensionality of the data,making the construced network can not be effectively interpreted from the perspective of neurology.Even more importantly,due to the large scale of the high-order functional connectivity network,it is verytime-comsuming to use some complex network or graph theory to calculate some topological properties.Therefore,this paper proposed a method for constructing a high-order minimum spanning tree network,calculated the traditional quantifiable network properties (degree and eccentricity),and used frequent subgraph mining technology to capture the discriminative subnetworks as features.Then,this paper applied a multi-kernel learning technique into the corresponding selected features to obtain the final classification results.The experimental results show that the classification accuracy is up to 97.54%.

Key words: Slow-order functional connectivity network, High-order functional connectivity network, Minimum spanning tree, Frequent subgraph

CLC Number: 

  • TP181
[1]POWERJ D,COHEN A L,NELSON S M,et al.Functional network organization of the human brain[J].Neuron,2011,72(4):665-678.
[2]ALEXANDER-BLOCH A F,GOGTAY N,MEUNIER D,et al.Disrupted modularity and local connectivity of brain functional networks in childhood-onset schizophrenia[J].Frontiers in Systems Neuroscience,2010,4:147.
[3]YANG G F,ZHANG Q,ZHANG Y T,et al.An fMRI Study of Aberrant Brain Network in Schizophrenia Patients[J].Chinese Journal of Clinical Psychology,2009,17(5):581-583.(in Chinese)
[4]HE Y,CHEN Z,EVANS A.Structural insights into aberranttopological patterns of large-scale cortical networks in Alzheimer’s disease.
[J].Journal of Neuroscience,2008,4(4):4756-4766.
[5]VAND E,DOUW L,BAAYEN J C,et al.Long-term effects of temporal lobe epilepsy on local neural networks:a graph theoretical analysis of corticography recordings[J].Plos One,2009,4(11):e8081.
[6]INOKUCHI A,WASHIO T,MOTODA H.An Apriori-BasedAlgorithm for Mining Frequent Substructures from Graph Data[C]∥Principles of Data Mining and Knowledge Discovery,European Conference(Pkdd 2000).Lyon,France,DBLP,2000:13-23.
[7]DAMARAJUE,ALLEN E A,BELGER A,et al.Dynamic functional connectivity analysis reveals transient states of dysconnectivity in schizophrenia[J].Neuroimage Clinical,2014,5:298-308.
[8]ZHANG H,CHEN X,SHI F,et al.Topographical Information-Based High-Order Functional Connectivity and Its Application in Abnormality Detection for Mild Cognitive Impairment[J].Journal of Alzheimers Disease Jad,2016,54(3):1095-1112.
[9]CHEN X,ZHANG H,GAO Y,et al.High-order resting-statefunctional connectivity network for MCI classification[J].Human Brain Mapping,2016,37(9):3282-3296.
[10]JACKSONT S,READ N.Theory of minimum spanning trees.I.Mean-field theory and strongly disordered spin-glass model[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2009,81(1):021130.
[11]BAO J,LU L,JI Z H.Tourism transportation optimization and tour route designing of north anhui province based on the kruskal algorithm of graph-theory[J].Human Geography,2010(3):144-148.(in Chinese)
[12]WU Z,BRAUNSTEIN L A,HAVLIN S,et al.Transport in weighted networks:partition into superhighways and roads.
[J].Physical Review Letters,2006,96(14):148702.
[13]DEMURU M,FARA F,FRASCHINI M.Brain network analysis of EEG functional connectivity during imagery hand movements[J].Journal of Integrative Neuroscience,2013,12(4):441-447.
[14]VOURKAS M,KARAKONSTANTAKI E,SIMOS P G,et al.Simple and difficult mathematics in children:a minimum spanning tree EEG network analysis[J].Neuroscience Letters,2014,576:28-33.
[15]LEE U,KIM S,JUNG K Y.Classification of epilepsy typesthrough global network analysis of scalp electroencephalograms[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2006,73(4 Pt 1):041920.
[16]TIJMSB M,WINK A M,DE H W,et al.Alzheimer’s disease:connecting findings from graph theoretical studies of brain networks[J].Neurobiology of Aging,2013,34(8):2023-2036.
[17]BORCHARDTV,LORD A R,LI M,et al.Preprocessing strategy influences graph-based exploration of altered functional networks in major depression[J].Human Brain Mapping,2016,37(4):1422-1442.
[18]FEI F,WANG L P,JIE B,et al.Discriminative subgraph mining with application in MCI classification[J].Journal of Nanjing University(Natural Sciences),2015,51(2):328-334.(in Chinese)
[19]DU J,WANG L,JIE B,et al.Network-based classification ofADHD patients using discriminative subnetwork selection and graph kernel PCA[J].Computerized Medical Imaging & Gra-phics the Official Journal of the Computerized Medical Imaging Society,2016,52:82-88.
[20]WANG L,FEI F,JIE B,et al.Combining Multiple NetworkFeatures for Mild Cognitive Impairment Classification[C]∥IEEE International Conference on Data Mining Workshop.IEEE,2014:996-1003.
[21]FRISTON K J.Statistical Parametric Mapping:The Analysis of Functional Brain Images[J].Neurosurgery,2013,61(1):216-216.
[22]TZOURIOMAZOYER N,LANDEAU B,PAPATHANASSIOU D,et al.Automated anatomical labeling of activations in SPM using a macroscopic anatomical parcellation of the MNI MRI single-subject brain[J].Neuroimage,2002,15(1):273-289.
[23]TEWARIEP,VAN D E,HILLEBRAND A,et al.The minimum spanning tree:an unbiased method for brain network analysis[J].Neuroimage,2015,104:177-188.
[24]KRUSKAL J B.On the shortest spanning subtree of a graph and the traveling salesman problem[J].Proceedings of the American Mathematical Society,1956,7(1):48-50.
[25]LOPESR H C.Kolmogorov-Smirnov Test[J].International Encyclopedia of Statistical Science,2008,10(1):718-720.
[26]BENJAMINI,YOAV,HOCHBERG Y,et al.Controlling the False Discovery Rate:A Practical and Powerful Approach to Multiple Testing.Royal Statistical Society.Series B (Me-thodological),1995,57(1):289-300.
[27]POLAJNAR M,DEMSAR J.Small network completion using frequent subnetworks [J].Intelligent Data Analysis,2015,19(1):89-108.
[28]YAN X,HAN J.gSpan:Graph-Based Substructure Pattern Mi-ning[C]∥IEEE International Conference on Data Mining.IEEE Computer Society,2002:721.
[29]LANCKRIETG R G,CRISTIANINI N,BARTLETT P,et al.Learning the Kernel Matrix with Semi-Definite Programming.
[C]∥Nineteenth International Conference on Machine Lear-ning.Morgan Kaufmann Publishers Inc.2002:323-330.
[30]SHERVASHIDZE N,SCHWEITZER P,VAN LEEUWEN E J,et al.Weisfeiler-Lehman Graph Kernels[J].Journal of Machine Lear-ning Research,2011,12(3):2539-2561.
[31]GUO H,LIU W Z,LIU Z F,et al.Difference index analysis on resting state functional brain network and its application in major depressive disorder classification[J].Computer Applications &Software,2014(12):85-88.(in Chinese)
[32]SACCHETM D,CAMACHO M C,LIVERMORE E E,et al.Accelerated aging of the putamen in patients with major depressive disorder[J].J Psychiatry Neurosci,2017,42(3):164.
[33]QIAO L,ZHANG H,KIM M,et al.Estimating functional brain networks by incorporating a modularity prior[J].Neuroimage,2016,141:399-407.
[34]M-L W,DONG C,ANDREEV V,et al.Prediction of susceptibi-lity to major depression by a model of interactions of multiple functional genetic variants and environmental factors[J].Mol Psychiatry,2012,17(6):624-633.
[1] HONG Rui, KANG Xiao-dong, LI Bo, WANG Ya-ge. Image Shape and Texture Description Method Based on Complex Network [J]. Computer Science, 2018, 45(11A): 244-246.
[2] ZHU Qing-sheng, DUAN Lang-jun and YANG Li-jun. Prototype Selection Algorithm Based on Natural Neighbor and MST [J]. Computer Science, 2017, 44(4): 241-245.
[3] . GC-BES:A Novel Graph Classification Approach Based on Embedding Sets [J]. Computer Science, 2012, 39(6): 155-158.
[4] WANG Gui-juan,YIN Jian,ZHAN Wei-xu. Feature Subgraph Selection Strategy Based on Category Information [J]. Computer Science, 2011, 38(8): 169-170.
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .