The network is generated in two steps. First, any node is assigned to a module Mi with a probability ��i, where �� = (��1, ��2,��, ��K) satisfies ��i=1K��i = 1. Then any two nodes u, v V and u Mi, v Mj are connected with probability Pi,j depending inhibitor CHIR99021 on Mi, Mj, and P is symmetric. If there is the modular structure in the network, then Pi,j < min Pi,i, Pj,j. With this model, the hierarchical structure of a network can be defined recursively. For any three modules Mi, Mj, and Mk, if Pi,j > max Pi,k, Pj,k, we say there is hierarchical structure among these three modules and Mi, Mj can be combined to a new module parallel to Mk.To construct the hierarchical structure, we use the bottom-up strategy. We first find all the possible modules on the lowest level and then build the hierarchical structure.
We use the method presented in [14] to find all the possible modules. Suppose K is given first. We let Nk denote the number of nodes in subnetwork Vk, Lkk denote twice the total number of edges in subnetwork Vk, and Lkl denote the total number of connections between the subnetworks Vk and Vl, where k, l = 1,2,��, K. The module identification problem is formulated asmax??P��(P)=��k=1KLkkNk?��k=1K?��l��kLklNk,(1)where P is a partition of the network.In matrix form, if we i=1,2,��,n,(2)the problem is formulated?letSik={1,if??node??i��Vk0,otherwise ��k=1KS?,k=1.(3)Here????for??i,j=1,2,��,K,?Si,j��0,1??=��k=1KS?,kT(2A?D)S?,kS?,kTS?,ks.t.?????asmax?��(S)=��k=1KS?,kTAS?,kS?,kTS?,k?��k=1K?��l��kS?,kTAS?,lS?,kTS?,k 1 is a vector with all elements being 1.
The objective function aims to both maximize the average degree within each module and minimize the average connections between different modules. We expect to achieve a good balance of the module size and make correct inference on the modules. The problem (3) is solved with an approximate method similar to the spectral clustering. We first compute the K eigenvectors of the matrix 2A ? D. By clustering these K eigenvectors as a matrix of n objects with K dimensions, we get the assignment of the n nodes into K modules.Now, we discuss how to determine the lowest level of all the possible modules K. For any node i V, the degree can be written asdi=��k=1Kdi(Vk),(4)wheredi(Vk)=��j��VkAij,(5)which defines the connections that node i has in the subnetwork Vk.
To determine the number of possible modules, we compare the average connectivity within a subnetwork AV-951 and the average connectivity between it and any other subnetwork. If the average connectivity within a subnetwork is greater, we take it as a module, that is,��i��Vkdi(Vk)Nk>l��k.(6)Alternatively, it can also be?��i��Vkdi(Vl)Nk, written asLkk>Lkl,(7)if we multiply both sides with Nk. This condition is very weak, thus with it, we hope we find all the modules as on the lowest level.