The mobile application discovery issue we face today suppresses revenue for app developers and enjoyment for users. I believe the solution likes not in creating a PageRank for applications, or a recommendation system based on downloads but a recommendation system based on usage patterns. As Hunch has shown with their curious correlations of cross consumption (for example: How Food Patterns Vary By Political Ideology), usage patterns are non-obvious.
Mobile applications stores should change in two ways to benefit application developers and users alike
First, shift to monthly and daily active users as engagement metrics, rather than downloads. Each metric on its own provides a timely sense of activity. Additionally, the ratio of these two is an insightful metric indicating a sticky factor. Cumulative downloads provides no engagement insight and can be easily gamed.
Second, provide a functional recommendation system, not so much like PageRank, but more like book or movie recommendations. Look no further than Netflix and Amazon, two other highly successful store fronts for a wide variety of products, as evidence of the power of such a system for both cross sales mechanisms and product offerings providing sustainable competitive advantage. And leverage stickiness and MAU/DAU data in the first example to power this recommendation system.
Apple recommending GoWalla if I have downloaded FourSquare is ineffective for everyone involved. Advertising can help the distribution problem, but the crux of the problem lies in the structure of the app stores.