Game-Theoretic Analysis of Network Community Structure
Donald Adjeroh, Umasankar KandaswamyAbstract: We study the problem of analyzing the community structure in complex networks using a game-theoretic framework. Nodes in the network are considered as players in an iterative non-cooperative game, and the nodes are then initially clustered based on the evolution of cooperation between the players. The initial communities are refined and verified using a hierarchical application of the energy landscape theory of alignments. The computational complexity of our approach is dependent on the number of nodes and the actual complexity of the network. Networks with simple community structures are easier and faster to analyze, while complicated networks, without clear-cut structures and possible overlaps take more time. On average, the complexity of the proposed approach is in n is the number of nodes, and O n K + η s logη c ηc (( )), where is the number of communities, ηs is the average number of nodes per community, and K is the number of game partners. Experimental results are shown for artificially generated random networks with known structures, the Zachary’s karate club network, and gene interaction network for a well-studied organism in molecular biology – E.coli.
Keywords:
network community structure, clustering, game theory, energy landscape model. network
doi:10.5019/j.ijcir.2004.112
Full Text PDF
^ TOP