We propose a modification model that can insert RCC into a network, while maintaining other structural properties of the original network (section ). Our model is reversible in that when operations are applied in reverse (deletion instead of addition of edges), the RCC can be removed from a network, while also maintaining the other structural properties. Our model only requires the information of the degree of the vertices, which is a much faster operation than computing the betweenness and closeness centralities.
<FIGURE>Definitions and Datasets
We briefly describe the definitions of the network properties and the test suite used for the experiments.
Definitions of network properties
Definition 1 \(k\) -core: Given a graph \(G(V,E)\) , where \(V,E\)  are the set of vertices and edges, a k-core is a maximal subgraph \(G_{k-core}\)  such that each node in \(G_{k-core}\) 
has degree at least k.

Definition 2 \(k\) -shell: Given a graph \(G(V,E)\) , a \(k\) -shell is the
induced subgraph over the maximal set of nodes such that (1)
the \(k\) -shell does not include nodes from any existing higher
shells, and (2) each node in the
\(k\) -shell has at least \(k\)  connections to nodes in the \(k\) -shell or
the higher shells.

The core number of a node is the highest value \(k\)  such
that the node is a part of a \(k\) -core. The \(k\) -core decomposition [1]} is the assignment of core numbers to nodes. Core numbers can be computed with complexity of \(O(|E|)\) .
To find a \(k\) -core, the \(k\) -core decomposition algorithm recursively removes nodes with degree less than \(k\) . We will denote all the nodes belonging to the \(k\) -core by the set \(C_k\) . Note that if \(G\)  is connected then \(C_1\)  is equivalent to the \(V\) . Subsequent inner cores are part of the outer cores i.e \( C_k \subset .....C_3 \subset C_2 \subset C_1 \subset V \)
Note that the \(k\) -core is the induced subgraph of the union
of \(j\) -shells for \(j \ge k\) . Hence the shells of the graph partitions the set \(V\)  into disjoint sets of vertices.
Definition 3 Expansion property [2]}: Given a graph \(G = (V, E)\)  where \(V\)  is the set of nodes and \(E\)  is the set of edges, the expansion of a set of nodes \(S \subset V\)  is a function of the number of nodes in \(V-S\)  to which \(S\)  is connected. That is, if \(N(S)\)  is the set of nodes to which \(S\)  is connected, then the expansion of \(S\)  is \(\frac{|N(S)|}{|S|}\)

A graph with a high value of expansion property is known as an expander graph. In an expander graph any subset \(S \in V \)  (where \( |S| \le \frac{V}{2} \) ) will have many neighbors. The expansion of a graph can be measured using the Cheeger constant, \(h(G)\) . A low Cheeger constant indicates a "bottle neck", i.e. the graph can be partitioned by removing very few edges. A high Cheeger constant indicates that no matter how the graph is partitioned, the number of edges across the partitions is always large.
Accurate calculation of the Cheeger constant is NP hard. For d-regular graphs it can be approximated by the second smallest eigenvalue of the spectrum of the normalised graph Laplacian given by \(L = I - D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\) . The second smallest eigenvalue \((\lambda _{2})\) , also known as the eigengap, is related to Cheeger constant by \(\frac{\lambda _{2}}{2} \le h(G) \le \@root  \of {2\lambda _2}\)  which is also know as Cheeger's inequality. It was shown in [3]} that the lower bound also holds for general graphs.

Test suite of networks
We used a diverse set of networks for our experiments. We used 8 real world networks that are publicly available [4]}, [5]}. We generated 15 synthetic networks of varying sizes and varying network core structures using the MUSKETEER synthetic network generation tool  [6]}. A summary of the properties of these 23 networks is given in Table REF . The \(\alpha \)  is the scale free exponent obtained after fitting the empirical degree distribution to a power law distribution which is given by \(p(k) \sim k^{-\alpha }\)  where \(p(k)\)  is the fraction of nodes having degree \(k\) . All the networks are considered to be undirected.
<TABLE>
Motivating Experiments
We present the experiments that motivated our research. We test whether vertices with high core numbers (i) have high centralities and (ii) can be used as seed nodes for community detection.
Correlation with other centrality metrics
Several papers [7]}, [8]}, [9]}, [10]}, [11]}, claim that the vertices with high core numbers should also have high centrality values. To test this claim, we compute the Jaccard coefficient (\(J_c\) ) given by \(\frac{S_1 \cap S_2}{ S_1 \cup S_2 }\)  between the set of vertices with highest core numbers (\(S_1\) ) and an
equal number of high ranked nodes for each of the centrality metrics (\(S_2\) ).
The results in Table REF  show a clear separation of the networks. In the first group, all the networks (blue) have high \(J_c\)  implying significant number of high central nodes also have highest core numbers. In the second group, (brown) the high core numbered nodes do not have high centrality as per the low \(J_c\)  scores.
<TABLE>
High core numbers to detect communities
In existing techniques of community detection utilizing \(k\) -core structure [12]},
the network is reduced to its \(k\) -core subgraph, for a predetermined value of \(k\) , and the communities in the subgraph are computed. The vertices in these communities are used as seed nodes to propagate the community information to other vertices.
We note that this process will succeed only if the communities are well represented in the reduced network. Therefore to test the applicability of this algorithm, we tabulate how the vertices in the innermost core are distributed across the communities.
Figure REF  plots the community ids of the networks in the x-axis and the number of nodes from the innermost core that are members of a particular community in the y-axis. We include all communities whose at least one vertex is in the innermost core.
We again observe a separation between two class of networks. In one group, the vertices from the innermost core are spread over multiple communities, whereas in the other group, the vertices from the innermost core are concentrated in one or two, communities. Clearly, the first group is more suitable for the community detection algorithm described earlier. Figure REF  shows the community distribution in the innermost core of two networks from our test suite. These results demonstrate that vertices with high core numbers are not always distributed across multiple communities, and in some cases can be concentrated in only one community.
<FIGURE><FIGURE>
Evidence of rich centrality club
These motivating experiments demonstrate the existence two groups of networks. One group consists of networks where the vertices from the inner cores have high correlation with vertices of different high centrality metrics and can be used as seed nodes for community detection. The other group consists of networks where the vertices from the inner cores have no correlation with other high centrality metrics, and are concentrated in one or two communities.
To visualize how rich centrality clubs are formed in the innermost cores, we divide the vertices in the network into two sets of nodes, based on whether they are part of the innermost core or not. We partition the nodes outside the innermost core into their respective communities and combine each community into a single supervertex. The set of nodes of the innermost core are also combined into a supervertex. Two supervertices are connected if there is at least one edge between the nodes comprising them.
<FIGURE>Figure REF  shows a visualization of the reduced network for two benchmark networks. Each node is labeled as \(c_x\)  for communities and \(k\)  for the innermost core. The supervertices are ordered by size with respect to average centrality(closeness and betweenness) of constituent vertices. For the network Caida, which is in the first group, the supervertex corresponding to the innermost core has significantly high centrality and is in the centre. For the network, Power, which was in the second group, there are no distinctively high centrality supervertex.
Since in the first group, the high centrality nodes are in the innermost cores and since by their definition these vertices are connected to each other, our experiments demonstrate that rich club of high centrality vertices is formed in these networks. In the next section, we present the topological property of these networks that lead to the formation of RCC.

Properties of Networks Containing Rich Centrality Clubs
We define structural properties of networks containing RCC and present empirical results to support our definition. In section  we provide theoretical rationale for our definition.
<FIGURE>Formal definition and rationale
Let the subgraph induced by the vertices in shell \(k\)  and their neighbors be \(S_{k}\) . Let \(d_k\)  be the average degree and \(n_k\) , the number of nodes in \(S_{k}\) . Let \(\lambda _{k}\)  be the second smallest eigen value of the normalized Laplacian matrix of \(S_{k}\) . Let the average distance of a vertex in shell \(S_a\)  to a vertex an inner shell \(C_{b}\) , \(a < b\) , be \(r_{ab}\) .
Given these parameters, we state that a network will contain a RCC if the following properties hold.

If for two shells \(k1\)  and \(k2\) , \(k1 < k2\) , then \(d_{k1} < d_{k2}\)  and \(n_{k1} > n_{k2}\) .

For all shells \(S_{k}\) , \(\lambda _{k} > \alpha \)

For all shells \(S_{k}\) , \(r_{kx} < \beta \) , where \(C_x\)  is a high numbered core, with density close to 1.

The first property requires that the shells have progressively smaller number of vertices, and become more dense from outer to inner shells. The second property provides the upper bound of the second smallest eigenvalue, and in turn, to the Cheeger constant at each shell. The higher \(\lambda _k\) , the more expander-like the associated shell. If the shell has multiple components, then each of them should maintain this property. The third property states that the hops to travel from the outer shells to inner cores should be small.
The values of the parameters \(\alpha \)  and \(\beta \)  are determined based on size and density of the whole network. As per our experiments, setting \(\alpha >.5\)  and \(\beta <4\)  can clearly distinguish between networks that contain RCC and those that do not.

Density of shells
The first condition is a feature of the core-periphery structure of almost all scale-free networks, whether they contain RCC or not. To demonstrate this, we first subdivide the vertices into subgraphs \(S_k\) . For each, we compute the average degree and the number of nodes. Since the number of shells varies across networks, for uniform presentation of the results we divide our results into three buckets. Starting from innermost we place the first \(25\%\)  shells in the first bucket(\(k_4\) ). The next \(25\%\)  falls in the second bucket(\(k_2\) ) and the final \(50\%\)  falls in the last bucket(\(k_n\) ). For each bucket we calculate the mean and the standard deviation of the average degrees and number of nodes classified in that bucket. These values are plotted in Figure REF (a) (average degree) and (b) (number of nodes). As seen from the figure with the exception of slight deviations, the first property is maintained in both sets of networks.

Eigenvalue of shells
For each \(S_k\) , we compute the normalized Laplacian (see section ), extract its spectrum using eigenvalue decomposition, and compute the eigengap. For each bucket as defined in the previous section, we calculate the average eigengap and the standard deviation. These values are plotted in Figure REF (c).
We observe that in graphs where we assume that RCC exists, there is a slow decline of the average eigengap. The Cheeger constant is high in the inner shells and gradually decreases from the inner to the outer shells. In the other group of networks, there is an abrupt fall in the average eigengap after the first bucket of inner shells. The first group can be bound by a large \(\alpha \)  than the second group, thus corroborating the second property.

Distance between shells
The third property enforces that on average two vertices in outer shells are more likely to be connected through inner dense shells. We show this in Figure REF , where in networks with an RCC, the average shortest distance of the nodes in the outer shells to the innermost (\(k_{max}\) ) and the second innermost shells (\(k_{max-1}\) ) is low (2-3) compared to networks without an RCC (10-50).
<FIGURE>
Application
In this section, we demonstrate how the presence of RCC can be leveraged in some important applications.
RCC as influential nodes
Vertices, which when selected as seed nodes can accelerate the diffusion process in networks are known as influential nodes. We hypothesize that the RCC, if present in a network, is a natural choice for the seed nodes for spreading. In order to test this hypothesis we execute a diffusion process adapted from [13]} on two groups networks in our dataset, i.e., those with an RCC and those without.
We choose a seed set size of \(\mathit {S}\) Our experiments with different value of \(\mathit {S}\)  yield similar results. (here we show results for \(\mathit {S}=10\) ) and populate this set preferentially on the basis of highly connected nodes which includes high centrality nodes (degree, closeness, betweenness), innermost shell nodes (these are nodes from within the RCC in networks that demonstrate its presence) and a random set of nodes. These set of seed nodes initially have an information and they pass it to all their neighbors using a flooding based broadcast approach (all neighbors of an informed vertex get informed).
This approach spreads the message very quickly and hence modified versions have been used in peer-to-peer networks for sending queries and searching [14]}. Although in real world systems this method is difficult to implement due to scalability issues, our goal here is to study how effective the vertices in the RCC are as seed nodes.
The x-axis in Figure REF  shows the fraction of vertices that have received the message and the y-axis the steps to reach these fraction of vertices. The networks form two groups. In one group that demonstrate the presence of RCC, the vertices from the innermost core are effective seed nodes for broadcasting and the time is comparable to the time when high centrality vertices are selected as seeds. The other group is when the vertices from the innermost core perform very poorly as seed nodes. The time to spread the information is equal to or worse than a random selection. These results show that only vertices in the innermost core in networks that demonstrate the presence of RCC are effective as seed nodes for spreading information.
<FIGURE>
Robustness
One of the desirable properties of a network is whether it can retain the ranking of its top-\(k\)  high centrality nodes under perturbation of the network. We hypothesize that networks which demonstrate the presence of RCC are robust to minor perturbations in the form of random deletion of edges.
To corroborate this we compute the closeness and the betweenness centrality based rankings of the nodes in the original network and compare the top-\(k\)  ranked nodes with that of the perturbed network. Perturbation is done by randomly deleting 1% to 8% of the edges from the original network. For comparison we use the standard Kendall \(\tau \)  measure as demonstrated in Laishram et. al. [15]}. As discussed in this work we also use \(k=50\) ; however, experiments with \(k=10, 20\)  etc., also yield similar results. Results obtained for both categories of networks, i.e., those in which an RCC is present and those in which it is not are illustrated in Fig REF .
Our results show that for minor perturbations of the topology, networks with RCC are robust in terms of preserving the top-\(k\)  high centrality nodes. However, if the perturbation intensity is too high the ranking gets jeopardized. In case of networks without an RCC even a small perturbation substantially disturbs the ranking of the top-\(k\)  high centrality nodes.
<FIGURE><FIGURE>
Algorithm for Forming RCC
We now present a simple yet effective modification algorithm for inserting RCC into a network and conversely removing RCC from a network containing it.
Rationale for the algorithm: To explain the rationale for our algorithm, we present two simplified models of a network with a RCC and without a RCC (Figure REF ). If the network contains RCC, then the inner shells are expander like, and communities meet at the RCC. An example model conforming to this structure would be a large clique in the center surrounded by smaller cliques.
In a network without a RCC, the majority of the communities do not meet through the inner core. This indicates that the inner core is not at any special position with respect to the paths connecting the communities. One example model of such a network would be a ring of cliques of different sizes. The smaller cliques can have connections between them. Here the highest core is at the side of the network rather than the centerWe emphasize that these models are only idealized representations of the two types of networks, and more complicated connections occur for real-world networks. Nevertheless the principal idea is maintained, i.e., for networks with a RCC, the innermost core is at the center of the network..
As per the example figure, to introduce a RCC, we can simply connect the high degree vertices across communities. The high degree of the vertices ensures that the clique (or near clique) formed by them will have higher core numbers. Joining communities ensures that the communities connect within this subgraph. In the network without an RCC in Figure REF , we would connect all the vertices in the ring.
Conversely, to destroy the RCC property of the network, we will simply delete the edges in the inner core, such that the connections between the communities are destroyed, and the highest numbered core moves away from the center.
Algorithm for forming RCC: Our proposed approach for connecting the communities via high degree vertices is however very expensive. This is because finding communities itself is a computationally intensive operation. A faster alternative is to simply connect (or disconnect) connections between the high degree vertices. This method works, because in networks without a RCC, high degree vertices within the same community are likely to be already connected. Therefore, any vertex pair connected as part of the modification algorithm will be in different communities.
Moreover, increasing the connections among the high degree nodes also brings all those (usually low degree) nodes that are neighbors of these high degree nodes closer in the network. Thus, the nodes in the innermost cores will have high centrality, as is a characteristic of networks with a RCC. On the converse side, for a network with a RCC, the high degree vertices will be in the inner core, so removing edges between them disconnects the cores.
It might seem from our approach that rich clubs of high degree vertices are also the rich centrality clubs. Figure REF  shows a counter example. The right hand graph has a rich club of high degree vertices but not a dense subgraph of high centrality vertices.
Experiments. The pseudocode of the algorithm is given in Algorithm . Figure REF , plots the eigengaps of the networks before (blue lines) and after (green lines) the modification. To clearly compare between the original and modified networks, we plot the eigengaps for each shell, rather than over an aggregate of shells as done in Figure REF (c).
Note that for the networks that demonstrate the presence of RCC (AS, Bible and Software), the eigengap of the modified network is smaller, i.e., the green line is lower and has a steeper slope than the original network. For the networks that do not demonstrate the presence of RCC (Power, Protein and Facebook), the green line is higher, showing that the value of the eigengap increased and has a more gradual slope. We report the statistics of the modified network in Table REF . The table clearly shows that our model also preserves the crucial structural properties of the original network, for e.g., the scale-free exponent \(\alpha \)  and the average degree.We set the model parameter \(h=30\) . The results are similar for \(h=20\)  and \(h=15\) . \(\gamma \)  is set to 0.2
<TABLE>

ParameterParameters
\(G (V,E)\) 
\(E\) 
\(h,\gamma , flag\) 

Sort vertices in G based on decreasing degree
Select the top \(h\)  nodes based on degree
\(flag==1\)  find \(E_1\)  possible edges that could be formed among the \(h\)  nodes
find \(E_1\)  actual edges that are present among the \(h\)  nodes
Select \(E_f\)  edges randomly from \(E_1\)  where \(|E_f| = \gamma * |E_1|\) 
flag == 1 \(E \leftarrow E \cup E_f \)  
\(E \leftarrow E - E_f \) 
\(E\) 
Algorithm for increasing \((flag==1)\) /decreasing (\(flag==0\) ) expansion property.
<FIGURE>
Theoretical insights of definition
We now theoretically demonstrate how the three properties described in section  lead to the formation of rich centrality clubs. We consider an ideal network, where the vertices of each shell form a connected component and as per property 2, the values of \(\alpha \)  are large enough such that each shell is an expander graph. Since an expander graph has no bottleneck, or clear partition, random graphs fulfill these criteria. We therefore assume that each subgraph, \(S_{k}\)  induced by a shell \(k\)  and its neighbors, is an Erdos-Reyni random graph, with \(n_k\)  vertices and \(d_k\)  average degree, and the probability of connection among a pair of vertices \(p_k\) ; thus, \(d_k \approx {n_k}{p_k}\) .
In [16]}, the authors prove several bounds on the average path length in a random graph \(G(n,p)\) . In particular, they state that if \(np \ge c > 1\) , then the average distance is constant times \(\frac{\log {n}}{\log {np}}\) . Using this result, we assume that the average distance between two vertices in subgraph \(S_k\)  is \(\frac{\log {n_k}}{\log {n_kp_k}} \approx \frac{\log {n_k}}{\log {d_k}}\) .
Now consider a path between two vertices \(v_1\)  and \(v_n\) , with the sequence of vertices \(v_1, v_2, \ldots , v_x, \ldots , v_{n-1}, v_n\) . Let the core numbers of these vertices be \(l_1, l_2, \ldots l_x, \ldots l_{n-1}, l_n\) . Let \(l_x\)  be the highest numbered shell in this sequence. We assume that for all shortest paths between \(v_1\)  and \(v_n\) , \(l_1 \le l_2 \le \ldots l_x \ge \ldots l_{n-1} \ge l_n\) .
This means that the shortest paths travel monotonically from a source low shell to the highest shell required, and then
back from the high shell to the destination low shell. Note that this assumption allows the path to remain in the same shell throughout as well. However, paths that zig-zag from a high shell to a low shell and back to a high shell are not allowed. This rationale is based on the fact that since lower valued shells are sparser, it is more likely that the paths will connect through higher shells than lower shells.
With these assumptions in place we can state the following

If there exists a shell \(k_{x}\) , such that, \(\frac{\log {n_{k_y}}}{\log {d_{k_y}}} > r_{yz}+ \frac{\log {n_{k_z}}}{\log {d_{k_z}}} \) , for all \(k_y < k_x\)  and for at least one \(k_z \ge k_x\) , then high centrality vertices are located in core \(C_{x}\) .
Let \(k_x\)  be the lowest numbered shell that satisfies the equation in the lemma. Consider the path between two vertices \(v\)  and \(u\) . If either \(v\)  or \(u\)  is in \(C_x\) , then the path between them has to pass through \(C_x\) . If neither of the vertices are in \(C_x\) , we have to consider two cases.
First case, the two vertices in the same shell \(k_a\) , \(x > a\) , then on average, the distance between them will be \(\frac{\log {n_{k_a}}}{\log {d_{k_a}}}\) .
Second case, the vertices from two different shells \(k_a\)  and \(k_b\) , \(x > a > b\) . On average the length of the shortest path will be \(r_{ba}+ \frac{\log {n_{k_a}}}{\log {d_{k_a}}}\) . This value is greater than the path simply going through \(k_a\) .
Thus for both cases, if \(\frac{\log {n_{k_a}}}{\log {d_{k_a}}} > r_{ax}+ \frac{\log {n_{k_x}}}{\log {d_{k_x}}} \) , the shortest path between any two vertices in the graph is on average going to pass though \(C_x\) . Thus the core \(C_x\)  will contain high closeness and betweeness centrality vertices.
As per property 1, \(n_y > n_x\)  and \(d_y < d_x\) , where \(k_y <k_x\) . Therefore the condition \(\frac{\log {n_{k_y}}}{\log {d_{k_y}}} > \frac{\log {n_{k_x}}}{\log {d_{k_x}}} \)  will hold for any two shells. To maintain the condition of the lemma, we have to ensure that the distance from the steps to go from one shell to another, \(r_{yz}\) , is small enough. In other words, the steps to go from shell \(y\)  to core \(z\)  is smaller than the difference of their average distance. We have observed that for networks with RCC, \(r_{yz}\) , where \(z\)  is the innermost or second innermost core, the value is between 2-4. The number of nodes in the outer shells can go upto thousands, thus easily satisfying the condition.
It might seem that because finding the eigen value is an expensive operation, identifying networks with RCC would also be more expensive than simply finding the high centrality vertices. However, note that our lemma is based on the average path per shell. This metric can be computed in parallel for each shell, and is faster than computing the centralities over the whole network.

Related Work
In this paper, we bring together several concepts from rich clubs, to core-periphery structure, to its application in information spreading and community detection, to expander graphs. To the best of our knowledge, this is the first paper to combine these different concepts within a single framework.
Rich club:
Rich club structure is well studied in the context of infrastructure networks [17]}, [18]}. Rich clubs have also been shown to emerge in biological networks as well, e.g., brain networks, metabololic networks [19]}, [20]}. One of the recurring themes of research on characterizing rich club structure has been focused on distinguishing degree associativity and the rich club structure.
Detection of cores: Algorithmic detection of core periphery introduced by [21]} is one of the most promising new area in network analysis. Several works such as [22]}, [23]} have presented that automatic techniques of separating the core nodes from the sparse periphery.
Batagelj and Zaversnik [24]} proposed a \(k\) -core decomposition algorithm that requires \(O(max(|E|, |V|))\)  runtime and \(O(|E|)\)  space. In [25]}, [26]} the authors proposed modifications of the previous linear approach which scales the computation to millions of nodes and billions of edges. In many networked systems, we are only concerned with estimating the importance of a subset of nodes instead of the entire network. In [27]}, the authors proposed a computation technique for computing the coreness for a node \(u\)  which only takes into account its \(\delta \)  neighborhood. Model based approaches have been presented in [23]}, [29]} where the authors designed objective functions to estimate the coreness of nodes.
Correlation of coreness with centrality measures: Coreness has been shown to be correlated with several centrality metrics. A strong Spearman's rank correlation between degree and coreness has been presented in [30]}, [31]} and the authors developed an anomaly detection system based on this correlation. In contrast, in[32]} showed that core number has low Pearson's correlation with centrality metrics such as degree, closeness and betweenness. An explanation could be that while many nodes in the network could potentially have the same core number, they would typically tend to be different in terms of the centrality measures and thus Pearson's correlation would be low. A more accurate comparison would be to consider the overlap of the top ranked nodes based on core numbers and other centrality metrics, which is what we do here.
Coreness for community detection: \(k\) -core decomposition outputs an ordered partition of the graph after processing it hierarchically. In [33]}, the authors proposed that this hierarchical information can be utilized by any graph clustering algorithm to obtain more meaningful partitions. In [12]}, the authors proposed a framework to accelerate label computation for nodes by modularity maximization utilizing the \(k\) -core information. They estimate a maximum speedup of \(80\%\)  through rigorous experiments.
Coreness for spreading: The core number though derived from degree, is a better indicator of the capacity for information dissemination. Strategically placed nodes, as detected by the \(k\) -core decomposition are able to spread information to a larger portion of the graph. This result has been shown by several works such as [35]}, [36]}, [37]}. In [38]}, [39]}, [40]}, the authors apply \(k\) -truss decomposition which is a triangle based extension of \(k\) -core decomposition, with the objective of finding a refined set of influential nodes from all potential high core nodes. The authors show that \(k\) -truss decomposition extracts influential spreaders which can infect a large portion of target nodes within first few steps of the SIR epidemic model.
Expander graphs: Analyzing graphs using spectral techniques has a long history [13]}, [42]}. The main idea behind these approaches is to consider information about the spectrum of a matrix representation of the graph (mainly, the adjacency matrix or the Laplacian). It has been presented by several researchers [43]}, [44]}, [45]} that expansion properties of the graph provide crucial signals in understanding the degree of cohesion in the underlying subgraph structure. High expansion property results in being simultaneously sparse and tightly connected. A graph with such non-trivial structural property are called expander graphs and a comprehensive review on this topic can be found in [46]}

Conclusion
We study the properties of networks that demonstrate the presence of rich club of shortest path based high centrality nodes. We find that in these network, the vertices of the innermost core constitute the rich centrality club. Our main observations are as follows.

The rich centrality clubs, if formed, are located in the inner cores of the network. These nodes can also be used as seed nodes for community detection.

The networks with RCC typically have cores with expander-like structures. The density of the cores increase from inner to outer. The average number of hops to travel from an outer core to an inner core is small (2-4 hops).

The nodes in the RCC of a network constitute very effective seeds for information diffusion. Further, presence of an RCC makes a network very resilient to small random structural perturbations.

A simple model can convert a network with an RCC to a one without an RCC and vice versa. The model has just two global parameters to be tuned and builds on the idea of increasing the density/sparsity of connections among high degree, i.e., the innermost core nodes.

Our experiments provide for the first time a deeper understanding about the rich club of high centrality vertices and their interplay with the core-periphery structure. In future, we aim to study dynamic networks to observe the evolution of RCCs over time.
