When News.me, a New York-based company, acquired some assets of the earliest social news sharing service Digg and refocused on Digg, its chances to make it were seen as a long shot. And while that dark prognosis hasn’t changed, Digg has come up with a business model — making app discovery easier — that could set it on the right path and in the process show others a new way of doing business.

Back in the day, when Digg was still a dominant force on the web, the company essentially came up with the “sponsored story links as an ad-unit” concept that proved to be quite successful, since it fit in with the overall usage behavior of Digg’s community. The new Digg has taken that concept and applied it to mobile apps. They call this “Apps We Love.” Apps that meet Digg’s criterion will pay an undisclosed amount of money to be featured.

Along the grain advertising

Digg General Manager Jake Levine say that the two apps that have been featured in tests so far — Zapd and Tapestry — have seen between two percent to four percent click-through rates on about 250,000 impressions per ad across the web and mobile platforms, which higher rates on mobile devices.

The click-through rate mirrors the click throughs on services such as BuzzFeed, which have taken a similar “content as advertising” approach. This approach has been a subject of great debate for a long time and will continue to be debated in context of traditional media publications.

John Borthwick, the co-founder and CEO of Betaworks, the main backer of Digg believes that as the content and media types continue to evolve, Internet advertising has to take an along-the-grain approach; as he defines it, “along the grain” means where advertising matches the service. For example, Google AdWords offered a utility not too different than its unpaid search results, which lead to better usage of advertisements. It turned out to be a big hit and the company has benefitted deeply from it. Twitter has started pushing promoted tweets that are very much in sync with its un-paid behavior. Borthwick believes that since Digg helped discovery of news stories, taking the promote-the-app route is an obvious move for the company.

App discovery is broken

Digg is part of a growing number of services that are trying to arbitrage the near-term inefficiency in the app market. Yesterday there was news that since Apple launched its app store, it had approved over a million apps. The Android app market is growing at a breakneck speed as well. All this growth has made discovery of apps very difficult.

Today, if a developer wants to get attention for her app, she has to bank on a few things to go right: Apple (or Google) features them on their App store — which is a long shot unless the app is exceptional — or the app is written up on the many blogs that cover apps. The problem is that while press attention is good, it doesn’t necessarily translate into millions of users. Discovery is a difficult and tedious process.

In an interview with the New York Times, Brewster Kahle, founder of the Internet Archive, a nonprofit digital library, put it succinctly when he said, “If someone else controls the distribution of your work, and the pricing, then you don’t have a company, you have an affiliate.” The New York Times also pointed out that while there are Instagram and Angry Birds, there also hundreds of thousands who don’t make much money from Apple’s app platform.

Inefficiency means opportunity

The market inefficiency has allowed companies like Paris-based AppsFire to thrive in the marketplace. The company yesterday launched its app discovery engine that takes on Apple’s app store itself. It is betting that its app will provide a better experience that Apple’s App Store, which has gone through some design changes (based on its Chomp acquisition)  — not necessarily for the better. If you had to draw an analogy, then AppsFire could be the LinkExchange of mobile.

The situation isn’t very different from the early days of the web when many web publications were started but eventually cratered because they were unable to build a big following. Discovery and attention are still vital criteria for success. And apps are essentially the mobile equivalent of the web destinations. Just as Expedia and Trulia spend dollars attracting traffic to their website, they would need a smarter way to get people to try their apps as well.

Like Digg and Appsfire we are going to see more people take a gander at the app marketplace. My colleague Ryan Kim has written about the growing number of startups that have jumped into the app discovery game. Facebook executives tout their ability to become king-makers for mobile apps, and back in the day Facebook were offering SocialCam as a poster child of success.

However, the market should be ripe for a strong push from an ad-based company that is not beholden to a major mobile platform. And that company is Yahoo (s YHOO), which under new CEO Marissa Mayer is looking to mobile as a big opportunity to reinvent itself. Last year they embarked on an app-discovery effort, but for now it has not yielded any major results. Maybe they should restart by snagging Appsfire and building an app-network. And as for Digg — it yet might live again.