We define and analyze a multi-agent multi-armed bandit problem in which\ndecision-making agents can observe the choices and rewards of their neighbors.\nNeighbors are defined by a network graph with heterogeneous and stochastic\ninterconnections. These interactions are determined by the sociability of each\nagent, which corresponds to the probability that the agent observes its\nneighbors. We design an algorithm for each agent to maximize its own expected\ncumulative reward and prove performance bounds that depend on the sociability\nof the agents and the network structure. We use the bounds to predict the rank\nordering of agents according to their performance and verify the accuracy\nanalytically and computationally.\n