تسجيل الدخول

تسجيل

Caveman Graph

المؤلف:  Watts, D. J.

المصدر:  Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton, NJ: Princeton University Press, 1999.

الجزء والصفحة:  ...

4-3-2022

2356

Caveman Graph

 

The (connected) caveman graph is a graph arising in social network theory formed by modifying a set of isolated -cliques (or "caves") by removing one edge from each clique and using it to connect to a neighboring clique along a central cycle such that all  cliques form a single unbroken loop (Watts 1999). A number of cavemen graphs formed in this manner from  are illustrated above.

Caveman graphs are perfect.

Caveman graphs will are implemented in the Wolfram Language as GraphData[{" src="https://mathworld.wolfram.com/images/equations/CavemanGraph/Inline4.svg" style="height:22px; width:6px" />"Caveman", {" src="https://mathworld.wolfram.com/images/equations/CavemanGraph/Inline5.svg" style="height:22px; width:6px" />n, k}" src="https://mathworld.wolfram.com/images/equations/CavemanGraph/Inline6.svg" style="height:22px; width:6px" />}" src="https://mathworld.wolfram.com/images/equations/CavemanGraph/Inline7.svg" style="height:22px; width:6px" />].

---

REFERENCES

Watts, D. J. Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton, NJ: Princeton University Press, 1999.

Watts, D. J. "Networks, Dynamics, and the Small-World Phenomenon." Amer. J. Soc. 105, 493-527, 1999.