MEASURING OPTIMAL CONNECTIONS IN LARGE NETWORKS: A NEW ALGORITHM AND ITS APPLICATIONS

Abstract

Researchers have identified several problems in measuring the strongest path connecting pairs of actors in valued graphs. To address these problems, it has been proposed that average path value be used to indicate optimal connections between dyads. However, a lack of proper computer algorithm and its implementation has hindered a wide-range application of the proposed solution. In this paper we develop a computer algorithm and fully implement it with four JAVA programs, which are available on request. These programs produce an optimal connection matrix, which is subsequently inputted into UCINET for further multidimensional scaling and clustering analysis. We demonstrate this procedure with a data matrix containing 38 organizations in information technology. We discuss the methodological implications of the application of our algorithm to future social network studies.

Keywords:

• Graph Theory
• Average Path Value
• Computer Algorithm
• Valued Graph

Direct all correspondences to Song Yang, at Dept. of Sociology, 211 Old main, Univ. of Arkansas, Fayetteville, AR, 72701, [email protected]. We thank David Knoke for providing helpful comments and his network dataset to this paper. We appreciated help from Steven Worden, Patrick Doreian and two anonymous reviewers, whose input improved the quality of our analyses. A grant from the Graduate Research Partnership Program in the College of Liberal Arts at University of Minnesota supported this project.