The high-level contributions of this paper are as follows: We modify an existing branch-andboundbased exact algorithm (for maximum clique size of an entire graph) to determine themaximal clique size that the individual vertices in the graph are part of. We then run thisalgorithm on six real-world network graphs (ranging from random networks to scale-freenetworks) and analyze the distribution of the maximal clique size of the vertices in these graphs.We observe five of the six real-world network graphs to exhibit a Poisson-style distribution forthe maximal clique size of the vertices. We analyze the correlation between the maximal cliquesize and the clustering coefficient of the vertices, and find these two metrics to be poorlycorrelated for the real-world network graphs. Finally, we analyze the Assortativity index of thevertices of the real-world network graphs and observe the graphs to exhibit positiveassortativity with respect to maximal clique size and negative assortativity with respect to nodedegree; nevertheless, we observe the Assortativity index of the real-world network graphs withrespect to both the maximal clique size and node degree to increase with decrease in thespectral radius ratio for node degree, indicating a positive correlation between the maximalclique size and node degree.
展开▼
