Dcs.warwick.ac.uk

Haojuan Tao#, Shuixia Guo#, Tian Ge#, Keith M. Kendrick#, Zhimin Xue, Zhening Liu∗, and Jianfeng Feng∗ Network communities refer to groups of vertices within which the connecting links are dense but between which they are sparse. A community mining algorithm aims at finding all the communities from a given network. Distinct from the exiting studies in the literature, our former developed community mining algorithm described in explored the notion of network communities and their properties based on the dynamics of a stochastic model naturally introduced. The relationship between the hierarchical community structure of a network and the local mixing properties of the stochastic model was established with the Let (V, E) denote a network, where V = {1, 2, · · · , n} is a set of n vertices and E is a set of links. In this study, a vertex in the network corresponds to a brain region, and a link between two vertices corresponds to the functional connectivity. Consider a stochastic process defined on the network, in which an agent freely walks from one vertex to one of its randomly selected neighbors along the links between them. Let X = {Xt, t ≥ 0} denote the positions of the agent, and P(Xt = i, 1 ≤ i ≤ n) be the probability that the agent hits the vertex i after t steps. Since the next state of the agent only depends on its previous state, P(Xt = it|X0 = i0, X1 = i1, · · · , Xt−1 = it−1) = P(Xt = it|Xt−1 = it−1).
Therefore, this stochastic process is a discrete Markov chain. Furthermore, it is also homo- geneous since its transition probability from vertex i to vertex j satisfies: where pij is a constant does not depend on t. In terms of the adjacent matrix of the network where P = (pij)n×n is the transition probability matrix, D = diag{d1, d2, · · · , dn}, and Now, let’s consider the dynamics of the above stochastic model defined on the network.
Intuitively, for a network with a community structure, its corresponding Markov chain will stick to some local mixing states or metastable states before reaches the global mixing state.
The topological information related to network communities can thus be inferred from the hitting and exiting times of the local mixing states. More specifically, for a well-formed community structure, each community is cohesive and easy to be locally mixed, corre- sponding to an early hitting time. On the other hand, few inter-community links lead to a late exiting time, or equivalently a long global mixing time. Let s1 denote the global mix- ing state and sn, · · · , s2, s1 be a sequence of local mixing states reaching to global mixing state. Let T ext, 1 ≤ s ≤ n be the exiting time of the s-th local mixing state. Following the main result of Large-deviation theory developed by Varadhan, Freidlin and Wenzel all local exiting times can be estimated by the spectrum of the Markov generator Q = I − P , where I is the identity matrix. Specifically, where 0 = λ1 ≤ λ2 ≤ · · · ≤ λn are the n non-negative real-valued eigenvalues of the generator Q. The hitting time of the s-th local mixing state can be reasonably estimated by the exiting time of the (s + 1)-th local mixing state, that is Therefore, any community structure of the network can be captured by the spectral proper- ties of the Markov generator Q. For a well-formed K-community structure, the cohesion is small, while a good separability of the community structure leads to the measure can be defined as the spectral signature of a network. It is clear that 0 ≤ CQk ≤ 1. A small CQK implies a better K-community structure with better cohesion as well as separability.
The number of well-formed communities can be inferred from From the above analysis, the connection between the community structure of a network and the spectrum of its corresponding Markov generator has been uncovered. Many ques- tions related to the characterizing the community structure of a network can be converted to observing and inferring from its spectral signature. See for a more complete discussion.
Many different strategies can be used to implement the mining of the K-community structure if some CQK is lower than a threshold. We follow the efficient implementation proposed in This algorithm does not require calculating the eigenvalues/eigenvectors and multiplying the transition matrix, which is thus suitable for very large-scale networks.
More detailed implementation of the scalable algorithm is described in Table S1: Treatment details of RMDD patients.
amitriptyline hydrochloride + sodium valproate Imipramine hydrochloride + sodium valproate All FEMDD patients were treatment na¨ıve. None of the RMDD patients receiving combination treatments had schizoaffective disorder or co-morbidity with any Axis II dis- orders. Combination treatments were being used due to their claimed efficacy for treatment [1] Yang B, Liu J, Feng J (2010) On the spectral characterization and scalable mining of network communities. IEEE Transactions on Knowledge and Data Engineering 99: http://doi.ieeecomputersociety.org/10.1109/TKDE.2010.233.
[2] Freidlin M, Wentzell A (1998) Random perturbations of dynamical systems, volume [3] Anderson I (2003) Drug treatment of depression: reflections on the evidence. Advances [4] Mahmoud R, Pandina G, Turkoz I, Kosik-Gonzalez C, Canuso C, et al. (2007) Risperi- done for treatment-refractory major depressive disorder. Annals of internal medicine [5] El-Khalili N, Joyce M, Atkinson S, Buynak R, Datto C, et al. (2010) Extended-release quetiapine fumarate (quetiapine XR) as adjunctive therapy in major depressive disorder (MDD) in patients with an inadequate response to ongoing antidepressant treatment: a multicentre, randomized, double-blind, placebo-controlled study. The International Journal of Neuropsychopharmacology 13: 917–932.
Table S2: Grey/white matter volumes of the ROIs involved in “hate circuit” for both patients (p) and normal controls (n).
Table S3: Grey/white matter volumes of the ROIs involved in risk/action circuit for both patients (p) and normal controls (n).
Table S4: Grey/white matter volumes of the ROIs involved in emotion/reward circuit for both patients (p) and normal controls (n).

Source: http://www.dcs.warwick.ac.uk/~feng/papers/mp_11_supp.pdf