Source author record

Randall A. LaViolette

Randall A. LaViolette appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

physics.data-an physics.soc-ph physics.chem-ph q-fin.TR

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2010arXiv

Sensitivity of the Performance of a Simple Exchange Model to its Topology

We study a simple exchange model in which price is fixed and the amount of a good transferred between actors depends only on the actors' respective budgets and the existence of a link between transacting actors. The model induces a simply-connected but possibly multi-component bipartite graph. A trading session on a fixed graph consists of a sequence of exchanges between connected buyers and sellers until no more exchanges are possible. We deem a trading session "feasible" if all of the buyers satisfy their respective demands. If all trading sessions are feasible the graph is deemed "successful", otherwise the feasibility of a trading session depends on the order of the sequence of exchanges. We demonstrate that topology is important for the success of trading sessions on graphs. In particular, for the case that supply equals demand for each component of the graph, we prove that the graph is successful if and only if the graph consists of components each of which are complete bipartite. For the case that supply exceeds demand, we prove that the other topologies also can be made successful but with finite reserve (i.e., excess supply) requirements that may grow proportional to the number of buyers. Finally, with computations for a small instance of the model, we provide an example of the wide range of performance in which only the connectivity varies. These results taken together place limits on the improvements in performance that can be expected from proposals to increase the connectivity of sparse exchange networks.

preprint2009arXiv

Tolerating the Community Detection Resolution Limit with Edge Weighting

Communities of vertices within a giant network such as the World-Wide Web are likely to be vastly smaller than the network itself. However, Fortunato and Barthélemy have proved that modularity maximization algorithms for community detection may fail to resolve communities with fewer than $\sqrt{L/2}$ edges, where $L$ is the number of edges in the entire network. This resolution limit leads modularity maximization algorithms to have notoriously poor accuracy on many real networks. Fortunato and Barthélemy's argument can be extended to networks with weighted edges as well, and we derive this corollary argument. We conclude that weighted modularity algorithms may fail to resolve communities with fewer than $\sqrt{W ε/2}$ total edge weight, where $W$ is the total edge weight in the network and $ε$ is the maximum weight of an inter-community edge. If $ε$ is small, then small communities can be resolved. Given a weighted or unweighted network, we describe how to derive new edge weights in order to achieve a low $ε$, we modify the ``CNM'' community detection algorithm to maximize weighted modularity, and show that the resulting algorithm has greatly improved accuracy. In experiments with an emerging community standard benchmark, we find that our simple CNM variant is competitive with the most accurate community detection methods yet proposed.

preprint2007arXiv

Community Detection via Facility Location

In this paper we apply theoretical and practical results from facility location theory to the problem of community detection in networks. The result is an algorithm that computes bounds on a minimization variant of local modularity. We also define the concept of an edge support and a new measure of the goodness of community structures with respect to this concept. We present preliminary results and note that our methods are massively parallelizable.

preprint1998arXiv

Quasi-chemical Theories of Associated Liquids

It is shown how traditional development of theories of fluids based upon the concept of physical clustering can be adapted to an alternative local clustering definition. The alternative definition can preserve a detailed valence description of the interactions between a solution species and its near-neighbors, i.e., cooperativity and saturation of coordination for strong association. These clusters remain finite even for condensed phases. The simplest theory to which these developments lead is analogous to quasi-chemical theories of cooperative phenomena. The present quasi-chemical theories require additional consideration of packing issues because they don't impose lattice discretizations on the continuous problem. These quasi-chemical theories do not require pair decomposable interaction potential energy models. Since calculations may be required only for moderately sized clusters, we suggest that these quasi-chemical theories could be implemented with computational tools of current electronic structure theory. This can avoid an intermediate step of approximate force field generation.